Data structure: Way of organizing data so we can efficiently use it.
Essential ingredients in creating fast and powerful algorithms.
Help to manage and organize data.
makes code cleaner and easier to understand.
Abstract data type: Is an abstraction of a data structure which provides only the interface to which a data structure must adhere to. Interface will not give any specifics to how something should be implemented or in what programming language.
ADT – Implementation(DS)
List – Dynamic Array, Linked list.
Queue – Linked List Based queue, Array based queue, Stack base queue
Map – Tree map, Hash map, Hash table
Computational complexity analysis:
How much time does this algorithm needs to finish the computation?
How much space does this algoritm needs to finish the computation?
Omega meta data
Big-O notation: Upper bound complexity of the worst case irrespective of the size of data(small data set or large data set)
n – The size of the input
Complexities ordered in from the smallest to largest.
Constant Time : O(1)
Logarithmic Time : O(log(n))
Linear time : O(n)
Linearithmic Time : O(nlog(n))
Quadric Time : O(nsquared)
Cubic Time : O(ncube)
Exponential Time : O(bpowern), b>1
Factorial Time : O(n!)
O(n + c) = O(n)
O(cn) = O(n), c > 0
f(n) = 7 log(n)3 + 15n2 + 2n3 + 8
O(f(n)) = O(n3) as n3 is the biggest value.