Abstract Data Type
What is a Data Structure?
A data structure is a way of organizing data so it can be used effectively.
Why Data Structure?
- Essential ingredients in creating fast and powerful algorithm.
- Help to manage and organize data.
- Make code cleaner and easier to understand
Abstract Data Type
- ADT is an abstraction of a data structure which provides only the interface to a data structure must adhere to.
- ADT does not give any specific details about how something should be implemented
Example
| Abstraction(ADT) | Implementation(DS) |
|---|---|
| List | Dynamic Array, Linked List |
| Map | Tree Map, Hash Map |
| Vehicle | Bicycle, Smart Car |
Computational Complexity Analysis
Complexity Analysis
- How many time does this algorithm need to finish?
- How many space does this algorithm need for its computation?
Big-O Notation
Big-O gives the upper bound of the complexity of worst case, helping to quantify performance as the input sie becomes arbitrarily large.
n = The size of the input
Complexity Term
Complexity ordered in from smallest to largest
| Term | Big-O Notation |
|---|---|
| Constant | $ O(1) $ |
| Logarithmic | $ O(log(n)) $ |
| Linear | $ O(n) $ |
| Linearithmic | $ O(nlog(n)) $ |
| Quadric | $ O(n^2) $ |
| Exponential | $ O(b^3), b > 1 $ |
| Factorial | $ O(n!) $ |
Example
Let $f$ be a function that describes the running the time of a particular algorithm for an input of size n:
$ f(n) = 7log(n)^3+15n^2+2n^3 + 8 $
Complexity analysis only cares about the worst case, the complexity of $f(n)$ will be
$O(f(n)) = O(n^3)$
More Examples
The following run in linear time: $O(n)$
$f(n) = n$
i := 0
While i < n Do
i = i + 1
$f(n) = n/3$
i := 0
While i < n Do
i = i + 3
The following run in Quadric time: $O(n^2)$
$f(n) = n*n = n^2$
For (i:=0; i < n; i = i + 1)
For (j:=0; j < n; j = j + 1)
Even change j:=0 to j:=n, the complexity still remains.
If i=0, we do n work, If i=1 we do n-1 work, etc...
For (i:=0; i < n; i = i + 1)
For (j:=n; j < n; j = j + 1)
So the question becomes what is: $(n) + (n-1) + (n-2) + (n-3)+...+3+2+1 $
Turns out to be $O(n(n+1)/2) = O(n^2/2 + n/2) = O(n^2)$
Again, complexity analysis only cares about the worst case, so the complexity would be $O(n^2)$
This also a $O(n^2)$ example. $O(f(n)) = O(n*(3n+2n)) = O(n^2)$
i := 0
While i < n Do
j = 0
While j < 3*n Do
j = j + 1
j = 0
While j < 2*n Do
j = j + 1
i = i + 1
Binary Search
Suppose we have a sorted array and we want to find the index of a particular value in the array, if it exists.
Time complexity below is $O(log(n))$.
low := 0
high := n - 1
While low <= high Do
mid := (low + high) / 2
If array[mid] == value: return mid
Else If array[mid] < value: low = mid + 1
Else If array[mid] > value: high = mid - 1
return -1