Why does one solution stay fast while another slows to a crawl as the input grows? Big O notation gives you the answer by tracking how an algorithm's work changes with input size. Use this cheat sheet to spot common patterns, compare solutions, and explain your choice clearly in an interview.
Table of Contents
- Step 1: Start With Input Size
- Step 2: Learn the Complexity Scale
- Step 3: Match Each Class to Code
- Step 4: Check Time and Space Separately
- Step 5: Keep the Dominant Term
- Step 6: Account for Best and Worst Case
- Step 7: Watch Recursion and Nested Loops
- Step 8: Use the Sheet During Interview Practice
- FAQ
Step 1: Start With Input Size
Every Big O notation cheat sheet begins with n, the number of items in the input. Ask what happens as n grows. Big O focuses on the growth pattern, not the exact clock time on one machine.
It also drops fixed details. A loop that performs 2n operations is still O(n). The factor 2 changes the work, but it doesn't change the growth class. The same rule turns n + 50 into O(n).
Step 2: Learn the Complexity Scale
The usual order, from easier to harder as n grows, is O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ), and O(n!). This is the core list to keep near your desk.
O(1) stays flat. O(log n) grows slowly because each step cuts the search space. O(n) visits each item. O(n log n) often appears in efficient sorting. O(n²) comes from comparing pairs. O(2ⁿ) and O(n!) quickly become costly.
For a visual reference, the Wikipedia explanation of Big O notation covers the formal idea behind asymptotic growth.
Step 3: Match Each Class to Code
Use these examples to connect symbols with code:
- O(1): Read
items[4]when the index is known. - O(log n): Use binary search on sorted data.
- O(n): Scan an array once to find a value.
- O(n log n): Run merge sort or heap sort.
- O(n²): Compare every pair with two loops over the same array.
- O(2ⁿ): Try every include-or-skip choice in a recursive subset search.
- O(n!): Test every possible visit order in a brute-force traveling-salesman-style problem.
The class describes growth, not quality by itself. A small O(n²) input may finish sooner than a large O(n log n) input. Still, the gap becomes important as the data set grows.
Step 4: Check Time and Space Separately
A sound Big O notation cheat sheet tracks both time and space. Time complexity measures work. Space complexity measures extra memory beyond the input.
An array lookup is O(1) time and usually O(1) extra space. A loop that builds a new array is O(n) time and O(n) space. A recursive function may run in O(n) time while using O(n) call-stack space.
Iteration can reduce stack use. But it may need its own data structure, such as a queue for breadth-first search. Write both results when an interviewer asks for full complexity.
Step 5: Keep the Dominant Term
To derive Big O, break the code into parts. Count each loop, identify repeated work, then keep the term that grows fastest.
For example, a function with one O(n) loop followed by one O(n²) loop has O(n + n²) work. The final answer is O(n²), because the quadratic term eventually dominates the linear term.
Two separate loops over the same input still produce O(n), not O(n²). A nested loop often produces O(n²), but only when both loops scale with n. If the loops use different inputs, the result may be O(nm).
One useful interview habit is to explain the discarded terms out loud. That shows you understand the simplification instead of memorizing a label.
Step 6: Account for Best and Worst Case
Big O usually refers to the worst-case upper bound. In a linear search, the target may appear in the first position, but it may also be missing. The worst case checks every item, so the answer is O(n).
Best-case and average-case results can still help. A search might be O(1) in the best case and O(n) in the worst case. State which case you're describing.
Hash map operations are often described as O(1) average or amortized time, but unusual collisions or resizing can change the cost of one operation. This is why precise wording matters. The Wikipedia overview of amortized analysis explains how a costly operation can be spread across a longer sequence.
Step 7: Watch Recursion and Nested Loops
Recursion does not automatically mean exponential time. A recursive binary search is O(log n) because each call cuts the remaining range in half.
By contrast, a recursive subset function may branch twice at each level. That pattern gives O(2ⁿ) time. A recursive traversal of a tree can be O(n) time when each node is visited once.
Nested loops need the same care. A sliding-window algorithm can contain an inner loop yet remain O(n), because each pointer moves forward and never revisits an item too many times. Count total pointer movement, not just indentation.
Step 8: Use the Sheet During Interview Practice
In a coding interview, write the complexity after your solution works. Name the input, state the time cost, then state the extra space cost.
For example: “The outer pointer moves across the array once. The inner pointer also moves forward across it, so total time is O(n). The window stores at most n items, giving O(n) space.” That answer is clearer than saying, “There are two loops, so it's O(n²).”
Phantom Code AI can help you practice this exact explanation during DSA and coding interview drills. Its guidance is useful when you want to compare a brute-force approach with a better one, then check the time and space analysis. You can also review DSA interview questions with complexity analysis as you work through problems.
For study, keep the sheet short. Include the seven main classes, one code pattern for each, and a note about space. If you're making course notes or internal documentation, check reuse rights before copying a full graphic.
FAQ
What is Big O notation in simple terms?
Big O notation describes how an algorithm's time or memory use grows as its input gets larger. O(1) stays constant, while O(n) grows with the number of items. It ignores fixed factors so you can compare growth patterns across machines and implementations.
What is the fastest Big O complexity?
O(1) is the best common complexity because its work does not grow with the input size. Reading an array element by a known index is a typical example. That label does not guarantee the lowest measured time for every small input, since hardware and fixed costs still matter.
Is O(n log n) better than O(n squared)?
O(n log n) usually scales better than O(n²) as n becomes large. Efficient comparison sorts often use O(n log n), while a pair-by-pair comparison uses O(n²). For a tiny input, the simpler quadratic method may still be fine.
How do I calculate Big O from code?
Count how often each part runs, then keep the fastest-growing term. One loop over n items is O(n). Two nested loops over the same n items are often O(n²). Drop constants such as 2n and fixed terms such as n + 10.
What is the difference between time and space complexity?
Time complexity measures how the number of operations grows. Space complexity measures extra memory used as the input grows. A recursive algorithm may have modest time but use stack space for each call, so interview answers should state both when asked.
Print a compact chart, then test yourself on code instead of memorizing symbols alone. For interview practice, use Phantom Code AI to explain why your answer has its time and space costs, and revise the solution until you can say the analysis in one clear paragraph.