Skip to main content
  1. Refs/

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)\)
Visualize time complexity
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
Rishi Maharaj
Sr. Software Engineering Manager

comments powered by Disqus