Big-O Time Complexity: Read It From the Code, Not From a Cheat Sheet
You can memorize a Big-O table, but then a new piece of code defeats you. The skill examiners test is reading complexity from the structure of the code. Here is how.
What Big-O actually says
Big-O describes how the number of steps grows as the input size n grows, ignoring constants and lower-order terms. A loop that does 3n steps and one that does 100n steps are both O(n): double the input and both do about double the work. A loop that does n² steps is in a different league: double the input and it does four times the work.
Reading it from code
O(1): constant
int first = arr[0];
The work does not depend on n. One step, whatever the array size.
O(n): one loop over the input
for (int i = 0; i < n; i++) {
sum += arr[i];
}
The body runs n times. Doubling n doubles the time. Linear search is this shape.
O(n²): a loop inside a loop
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
count++;
}
}
The inner body runs n × n times. Bubble sort, selection sort and insertion sort (worst case) are this shape. When n = 1000, that is a million steps; when n = 100 000, ten billion.
O(log n): the problem halves each time
while (n > 1) {
n = n / 2;
}
How many times can you halve n before reaching 1? About log₂ n. For n = 1 000 000 that is about 20 steps. Binary search is this shape: each comparison discards half of what is left.
O(n log n): do log n levels of n work
Merge sort splits the array in half repeatedly (log n levels) and does n work to merge at each level. Hence n log n. For n = 1 000 000 that is around 20 million steps, versus a trillion for O(n²).
Two rules for combining
- Sequential blocks add, then keep the biggest. A loop of n followed by a loop of n² is O(n + n²) = O(n²).
- Nested blocks multiply. A loop of n containing a loop of log n is O(n log n).
And always drop constants: O(2n + 5) is O(n).
How fast they grow
| n | log n | n | n log n | n² |
|---|---|---|---|---|
| 10 | ~3 | 10 | ~33 | 100 |
| 1 000 | ~10 | 1 000 | ~9 966 | 1 000 000 |
| 1 000 000 | ~20 | 1 000 000 | ~19 931 569 | 10¹² |
The jump from n log n to n² is the difference between "finishes in a second" and "finishes next week" for large inputs. That is why algorithm choice matters.
Best, average and worst case
The same algorithm can behave differently on different inputs.
| Algorithm | Best | Average | Worst |
|---|---|---|---|
| Linear search | O(1) | O(n) | O(n) |
| Binary search | O(1) | O(log n) | O(log n) |
| Bubble sort | O(n) (with early exit) | O(n²) | O(n²) |
| Merge sort | O(n log n) | O(n log n) | O(n log n) |
| Quick sort | O(n log n) | O(n log n) | O(n²) |
Unless the question says otherwise, "time complexity" in exams usually means the worst case.
Space complexity
The same idea applies to memory: how much extra space does the algorithm need as n grows? Merge sort needs O(n) extra space for merging. In-place sorts like heap sort need O(1). Recursion also uses stack space proportional to its depth.
Exam checklist
- Count how many times the innermost statement executes in terms of n.
- Identify loops that halve or double the variable: those are logarithmic.
- Add sequential parts, multiply nested parts, drop constants.
- State which case (best/average/worst) you are giving.
Sumantrak™ is an AI mentor built for Indian engineering, diploma, BCA and BSc CS/IT students — Data Structures, Algorithms, and the rest of your syllabus, explained like this. Free to start →