Data Structures and Algorithms
··2 mins
Table of Contents
Videos #
- Abdul Bari’s Algorithms (84 videos) - Great teacher, who walks you through concepts end-to-end. Videos 19 - 29 (Recurrence Relations) can safely be skipped. If there were any DS / Algo topics you never thoroughly understood, definitely recommend looking it up here and giving it a watch.
Time Complexity #
Ordering of complexities:
constant < logrithmic < linear < quadratic < cubic < exponential
\(1 < \log n < \sqrt{n} < n < n \cdot \log n < n^2 < n^3 < \ldots < 2^n < 3^n < \ldots < n^n \)
- Constant -
\(O(1)\) - Takes the same amount of time, regardless of input size
- get the first element of an array
- pop the last element off of a stack
- Logrithmic -
\(O(\log n)\) - Time taken increases very slowly as compared to input size increases
- height of a balanced binary tree
- binary search
- Linear -
\(O(n)\) - Input size and time taken increases at the same rate
- iterate on every item in an array
- Quadratic - \(O(n^2)\) - Time taken increases faster than growth in input size
- Cubic - \(O(n^3)\) - Time taken increases much faster than growth in input size
- Exponential - Time taken explodes with tiny increases in input size
- \(O(2^n)\)
- \(O(3^n)\)
- \(O(n^n)\)
Loop | Big O Time | Notes |
---|---|---|
for (i=0; i<n; i++) {} |
\(O(\log n)\) | Normal loop operating on every element once takes linear time |
for (i=0; i<n; i+2) {} |
\(O(\log n)\) | Skipping every other number is still linear time, because as the input grows, the time take still grows at a linear rate |
for (i=n; i>1; i--) {} |
\(O(\log n)\) | Normal loop going in reverse is still linear |
for (i=0; i<n; i*2) {} |
\(O(\log_2 n)\) | Multiplying by 2 reduces the number of times going through the loop, making it logrithmic (base 2) |
for (i=0; i<n; i*3) {} |
\(O(\log_3 n)\) | Similar to the above, except in this case it would be logrithmic (base 3) |
for (i=n; i>1; i/2) {} |
\(O(\log_2 n)\) | Similarly, dividing reduces the number of times the loop is called, making this logrithmic (base 2 |