What does Big-O tell you?
Big-O describes how a resource grows as the input grows. In interview settings, the resource is usually running time or extra memory. It does not predict exact milliseconds. It gives a growth-rate model that lets you compare approaches independently of a particular machine.
When we call a full array scan O(n), we mean doubling the number of items can roughly double the dominant work. Constant factors still affect real performance, but Big-O focuses on what keeps growing.
Define the input variable. For a grid, use m rows and n columns. For a graph, use V vertices and E edges.
Common Big-O growth rates
| Complexity | Growth story | Common example |
|---|---|---|
| O(1) | Fixed work independent of input size | Read an array element by index |
| O(log n) | Keep halving the remaining problem | Binary search |
| O(n) | Visit each item a constant number of times | One scan, two pointers, sliding window |
| O(n log n) | Logarithmic work across n items | Comparison sorting, repeated heap operations |
| O(n²) | Compare many pairs or nest linear work | All pairs, simple double loop |
| O(2ⁿ) | Branch on choices for each item | Unpruned include/exclude search |
These are not quality scores. An O(n²) solution may be the right answer for a small input or a problem that inherently produces O(n²) output. The constraints and required result matter.
How to read a solution outline
Sequential steps add
If the plan says “sort, then scan,” the time is O(n log n + n), which simplifies to O(n log n) because the dominant term grows faster.
Nested work multiplies
If one full loop happens inside another full loop over the same input, the work is O(n × n) = O(n²). But do not judge only by indentation: a sliding-window inner loop can still be O(n) total if its left boundary moves forward at most n times across the whole run.
Halving creates logarithms
Repeatedly cutting the active interval in half creates O(log n) rounds. If each round also performs an O(n) scan, the total may be O(n log n).
Branches form a search tree
When recursion makes two independent choices at each of n levels, the search tree can contain O(2ⁿ) states. Pruning, memoization, or a smaller branching factor can change the analysis.
Early exits do not change the worst case
A target may appear at the first index, but a linear search still has an O(n) worst case when the target is last or missing.
How to analyze extra space
Count memory created by the algorithm beyond the input and output. A few indexes and counters are O(1). A set that can hold every input value is O(n). A two-dimensional dynamic-programming table may be O(mn).
- Hash maps, sets, heaps: ask how many entries they can hold at the same time.
- Recursion: count the maximum call-stack depth, not the total number of calls.
- Copies and slices: language-level convenience operations may allocate new collections.
- Output: state whether you are reporting auxiliary space or including the required result.
A balanced-tree DFS may use O(log n) call-stack space, while a completely skewed tree can use O(n) stack space.
Four outline drills
Scan once with a seen set
Create an empty hash set, walk through the array, check membership, then insert. Expected time is O(n); the set can grow to O(n) extra space.
Narrow an interval by half
Keep left and right bounds, inspect the middle, and retain only one half. Time is O(log n); a few indexes use O(1) extra space.
Push every value into a heap
Insert n values and later remove many of them. Repeated O(log n) heap operations lead to O(n log n) time; the heap holds O(n) space.
Compare every later value
For each index, scan all later indexes. The shrinking suffix still sums to quadratic work: O(n²) time and O(1) extra space if no large helper structure is created.
Structure-specific shortcuts
Direct access is cheap; full scans are linear; shifting values is expensive; copying costs space.
A traversal often visits every node once; recursive space follows the maximum height.
Adjacency-list traversal is commonly O(V + E); representation determines neighbor-inspection cost.
Visiting each cell and a constant number of neighbors is O(mn), a grid-specific form of O(V + E).
Big-O interview checklist
- Define the input-size variables.
- Identify the operation that dominates the work.
- Count total advancement across loops, not only visible nesting.
- Draw the recursion tree or count subproblems when branches repeat.
- Add sequential stages, multiply genuinely nested stages, then keep the dominant term.
- Count helper collections, copies, and maximum recursion depth.
- State both time and auxiliary space, then explain them in one sentence each.
“The right and left boundaries each move forward at most n times, so the total traversal work is O(n), not O(n²). The frequency map can hold at most k distinct values, so extra space is O(k).”
Apply the analysis
See how repeated halving produces O(log n).
READ →DFS vs. BFSCompare O(V + E) traversal with different memory shapes.
COMPARE →Practice the reasoning
Build Big-O intuition inside each solution.
Cozytek Code connects the outline, code, edge cases, and time-space tradeoffs throughout the curriculum.
