Big O Cheat Sheet
AS
Anthony SandeshUnderstanding algorithmic complexity is crucial for writing efficient code and making informed decisions about data structures and algorithms. This cheat sheet covers the fundamentals of Big O notation, common time and space complexities, and real-world examples with code snippets.
What Is Big O Notation?
Big O notation describes the upper bound of an algorithm’s running time or space requirements in terms of the input size (typically denoted as n). It abstracts away constants and lower-order terms to focus on the most significant factors affecting performance as n grows.
- Time Complexity: How the runtime grows with input size.
- Space Complexity: How the memory usage grows with input size.
Common Time Complexities
Complexity | Name | Typical Use Cases |
O(1) | Constant | Accessing an array element by index |
O(log n) | Logarithmic | Binary search |
O(n) | Linear | Single loop over input |
O(n log n) | Log-Linear | Efficient sorting algorithms (e.g., mergesort, heapsort) |
O(n²) | Quadratic | Nested loops over the input |
O(2ⁿ) | Exponential | Recursive solutions to the Tower of Hanoi |
O(n!) | Factorial | Generating all permutations |
Common Space Complexities
Complexity | Name | Example |
O(1) | Constant | A fixed number of variables |
O(n) | Linear | Storing an array or dynamic list of size n |
O(n²) | Quadratic | Adjacency matrix for a graph with n vertices |
Cheat Sheet: Operations & Their Complexities
Operation | Time Complexity | Space Complexity |
Array indexing | O(1) | O(1) |
Hash table lookup/insertion/deletion | O(1) average | O(n) |
Stack/Queue push/pop | O(1) | O(n) |
Binary search | O(log n) | O(1) |
Quick sort (average) | O(n log n) | O(log n) |
Merge sort | O(n log n) | O(n) |
Bubble sort | O(n²) | O(1) |
Insertion sort | O(n²) | O(1) |
Matrix multiplication (naïve) | O(n³) | O(n²) |
Real-World Code Examples
1. Constant Time: O(1)
Accessing an element by index in a list.
2. Logarithmic Time: O(log n)
Binary search on a sorted list.
3. Linear Time: O(n)
Summing all elements in a list.
4. Log-Linear Time: O(n log n)
Merge sort implementation.
5. Quadratic Time: O(n²)
Checking for duplicates with nested loops.
Tips for Analyzing Complexity
- Drop Constants: O(2n) simplifies to O(n).
- Drop Lower-Order Terms: O(n + log n) simplifies to O(n).
- Worst, Average, Best: Be aware of different cases (e.g., quicksort has worst-case O(n²) but average O(n log n)).
- Space vs. Time Trade-offs: Sometimes using extra memory (e.g., a hash table) can reduce time complexity.
Conclusion
This cheat sheet provides a quick reference to Big O notation, helping you gauge the efficiency of algorithms and data structure operations. Keep it handy when designing and analyzing your code to ensure optimal performance.
Happy coding!
