Complexity Analysis
Big O Notation
Asymptotic Notation
- Big O notation (upper bound)
- Big Omega notation (lower bound)
- Big Theta notation (tight bound)
- Little o and little omega notation
- Understanding asymptotic behavior
Common Complexities
- O(1) - Constant time
- O(log n) - Logarithmic time
- O(n) - Linear time
- O(n log n) - Linearithmic time
- O(n²) - Quadratic time
- O(2ⁿ) - Exponential time
- O(n!) - Factorial time
Time Complexity
Analyzing Algorithms
- Counting operations
- Worst-case analysis
- Average-case analysis
- Best-case analysis
- Amortized analysis
Common Patterns
- Single loops: O(n)
- Nested loops: O(n²) or O(n*m)
- Divide and conquer: O(n log n)
- Recursive algorithms
- Iterative vs recursive complexity
Space Complexity
Memory Analysis
- Auxiliary space
- Input space
- Total space complexity
- Space-time tradeoffs
Common Space Complexities
- O(1) - Constant space
- O(n) - Linear space
- O(n²) - Quadratic space
- Recursive call stack space
Amortized Analysis
Concepts
- Amortized cost
- Aggregate method
- Accounting method
- Potential method
Examples
- Dynamic array resizing
- Hash table operations
- Union-Find data structure
Interview Questions
- What is the difference between Big O, Big Omega, and Big Theta?
- How do you analyze the time complexity of a recursive algorithm?
- Explain amortized analysis with an example.
- What is the space complexity of quicksort?
- How does space complexity differ from time complexity?
Coding Practice
- Analyze the time complexity of various sorting algorithms.
- Calculate space complexity for recursive algorithms.
- Perform amortized analysis for dynamic array operations.
- Compare time complexities of different search algorithms.
- Write code and analyze its complexity.
Resources
- "Introduction to Algorithms" - Chapter 3 (Growth of Functions)
- Big O Cheat Sheet: https://www.bigocheatsheet.com/
- Complexity Analysis Guide: https://www.geeksforgeeks.org/analysis-of-algorithms/