We need to learn how to compare the performance different algorithms and choose the best one to solve a particular problem.
- Time Complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the input. It tells us how well an algorithm will scale.
- The Big O notation is a way of expressing the complexity related to the number of items that an algorithm has to deal with
- Space Complexity of an algorithm quantifies the amount of space or memory taken by an algorithm to run as a function of the length of the input
| Time Complexity | Name |
|---|---|
| O(1) | Constant |
| O(logn) | logatirhmic |
| O(n) | linear |
| O(n logn) | n log-star n |
| O(n^2) | quadratic |
| O(2^n) | exponential |
| O(n!) | factorial |
- contiguous block in memory
- every element occupies the same amount of space in memory
- if we know the index of an element, the time to retrive the element will be the same
- retriving an element from an array is made in constant time O(1) if we know the index! If we don't know the index the time complexity to retrive an element is linear: O(n)
| Operation | Time complexity |
|---|---|
| Retrive with index | O(1) |
| Retrive without index | O(n) |
| Add an element to a full array | O(n) |
| Add an element to the end of an array (has space) | O(1) |
| Insert/Update an element at a specific index | O(1) |
| Delete an element by setting it to null | O(1) |
| Delete an element by shifting an element | O(n) |
- See geek-ref
- Divide and Conquere algorithm, splitting phase and merging phase
- splitting phase in in place, merging phase use a temp array
- has a time complexit of O(n logn): we are repeatedly dividing the array in half during the splitting phase
- there is a lot temp array created... be carefull if the memomory is an issue
- See geek-ref
- Divide and Conquere algo
- It picks an element as pivot and partitions the given array around the picked pivot.
- Target of partitions is, given an array and an element x of array as pivot, put x at its correct position in sorted array and put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x.