Visualized DSA Strategies

Episode 1 Big O

9 min · C++ · Quiz

Episode 1Big O

▶ This video is coming to YouTube soon.

Two solutions both give the right answer. Which one is better? Instead of timing code, we count its steps and watch how that count grows with the input. You'll see why Big O drops constants and keeps only the biggest term, meet the six growth classes from O(1) to O(2ⁿ), learn to read Big O straight from loops, and check whether an idea is fast enough from the problem's constraints, before writing it.

What you'll learn

  • Why we count steps instead of seconds
  • Best case vs worst case, and why Big O uses the worst
  • Drop the constants and keep the biggest term: 3n + 2 → O(n), n² + n → O(n²)
  • The growth ladder: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ)
  • Is it fast enough? About 10⁸ steps per second, and what n ≤ 10⁵ rules out
  • Reading code: loops in a row add, nested loops multiply, halving is O(log n), sorting is O(n log n)
  • Space complexity, and trading memory for time

Chapters

  1. 0:00Intro
  2. 0:16How to judge an algorithm
  3. 0:53Time complexity: count the steps
  4. 1:28Best case, worst case
  5. 1:55Drop the constants
  6. 2:23Keep only the biggest term
  7. 2:54The growth ladder: O(1) to O(2ⁿ)
  8. 3:22Is it fast enough? Reading constraints
  9. 4:02O(1) in code
  10. 4:29Loops in a row add
  11. 4:52Nested loops multiply: O(n²)
  12. 5:20Halving: O(log n)
  13. 5:44Sorting: O(n log n)
  14. 6:14Space complexity
  15. 6:50Time vs space
  16. 7:16Quiz: what's the Big O?
  17. 7:55Recap

Quiz: test yourself

The 4 questions from the end of the episode. Pick an answer to see why it's right.