# Data Structures and Algorithms

··2 mins

## 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 Author
Rishi Maharaj
Sr. Software Engineering Manager