Part I · Foundations, Programming and Algorithmic Thinking
4. Complexity, Memory and Performance Analysis
10 lessons•73 topics•Beginner
10 of 10 lessons published
4.015 animated
Asymptotic notation
- Big O
- Big Omega
- Big Theta
- little-o
- little-omega
- Upper and lower bounds
- Tight bounds
- Dominant terms
- Hidden constants
4.023 animated
Common growth functions
- O(1)
- O(log n)
- O(sqrt n)
- O(n)
- O(n log n)
- O(n²)
- O(n³)
- O(2^n)
- O(n!)
- Polynomial vs exponential
4.037 animated
Loop complexity
- Single loop
- Nested loops
- Non-uniform loops
- Halving and doubling
- Dependent loop bounds
- Triangular loops
- Two-pointer amortized loops
4.044 animated
Recurrence relations
- T(n)=T(n-1)+O(1)
- T(n)=2T(n/2)+O(n)
- Substitution
- Recursion tree
- Master theorem
- Akra-Bazzi overview
4.054 animated
Complexity scenarios
- Best case
- Average case
- Worst case
- Expected case
- Amortized analysis
- Input distribution
- Randomized algorithm bounds
4.063 animated
Amortized methods
- Aggregate analysis
- Accounting method
- Potential method
- Dynamic array doubling
- Stack multipop
- Union-find intuition
4.071 animated
Space complexity
- Auxiliary space
- Input space
- Recursion stack
- In-place algorithms
- Memory-time trade-off
- Peak memory
- Memory leaks
4.085 animated
Computer memory model
- Stack frames
- Heap objects
- Call stack
- References
- Object headers
- Garbage collection
- Cache locality
- CPU caches
- Cache lines
4.092 animated
Practical performance
- Benchmark harness
- Warm-up and JIT
- Allocation overhead
- Boxing
- String concatenation
- Branch prediction
- Iteration locality
4.102 animated
Complexity comparison
- Arrays vs linked lists
- Hashing expected/worst-case
- Balanced trees
- Sorting lower bound
- Graph adjacency list vs matrix