Big O Notation
Measuring algorithm speed. Why constants vanish. The complexity classes.
Lessons
1. Intro
(Why speed matters)
2. The Speed Problem
(Why execution time varies)
3. Input Size
(The key variable)
4. What Big O Means
(Worst-case upper bound)
5. Why We Ignore Constants
(Growth patterns matter)
6. Drop Lower-Order Terms
(Highest power dominates)
7. O(1) - Constant Time
(No loops needed)
8. Constant Time Example
(Array access)
9. O(n) - Linear Time
(One pass through data)
10. Linear Time Example
(Finding maximum)
11. Problem - Find Maximum
(Analyzing linear scan)
12. Find Maximum - Insight
(Single pass suffices)
13. Find Maximum - Algorithm
(Loop and compare)
14. Find Maximum - Implementation
(Implementation structure)
15. O(n²) - Quadratic Time
(Nested loops)
16. Quadratic Example
(Checking all pairs)
17. Quiz: Complexity Classes
(Knowledge check)
18. O(log n) - Logarithmic Time
(Halving search space)
19. Logarithmic Example
(Binary search)
20. O(n log n) - Linearithmic Time
(Efficient sorting)
21. Linearithmic Example
(Merge sort)
22. O(2^n) - Exponential Time
(Trying all subsets)
23. Exponential Example
(Naive Fibonacci)
24. O(n!) - Factorial Time
(All permutations)
25. Comparing Growth Rates
(Ranked by speed)
26. How to Analyze Code
(Counting loops)
27. Sequential Loops
(Addition rule)
28. Nested Loops
(Multiplication rule)
29. Problem - Two Sum
(Comparing O(n²) vs O(n))
30. Two Sum - Insight
(Hash map lookups)
31. Two Sum - Algorithm
(Single pass with map)
32. Two Sum - Implementation
(Hash map approach)
33. Space Complexity
(Memory usage)
34. Recursive Space
(Call stack depth)
35. Quiz: Space vs Time
(Knowledge check)
36. Amortized Analysis
(Average over sequence)
37. Best vs Worst Case
(When Big O varies)
38. Problem - Binary Search
(Analyzing logarithmic search)
39. Binary Search - Insight
(Divide and conquer)
40. Binary Search - Algorithm
(Shrinking window)
41. Binary Search - Implementation
(Iterative implementation)
42. Practical Analysis Tips
(Quick heuristics)
43. When Constants Matter
(Real-world tradeoffs)
44. Quiz: Analysis Practice
(Knowledge check)
45. Problem - Contains Duplicate
Compare time complexities
46. Contains Duplicate - Insight
Three approaches
47. Contains Duplicate - Algorithm
Hash set approach
48. Contains Duplicate - Implementation
The pseudocode
49. Section Recap
What we learned