← Computer Science blog
Concept guide19 October 2026 · 3 min read

Big-O Time Complexity: Read It From the Code, Not From a Cheat Sheet

CSEITAI&DSR&AIBCABSc CSBSc ITCO+2

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

  1. Sequential blocks add, then keep the biggest. A loop of n followed by a loop of n² is O(n + n²) = O(n²).
  2. 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

nlog nnn log nn²
10~310~33100
1 000~101 000~9 9661 000 000
1 000 000~201 000 000~19 931 56910¹²

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.

AlgorithmBestAverageWorst
Linear searchO(1)O(n)O(n)
Binary searchO(1)O(log n)O(log n)
Bubble sortO(n) (with early exit)O(n²)O(n²)
Merge sortO(n log n)O(n log n)O(n log n)
Quick sortO(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

  1. Count how many times the innermost statement executes in terms of n.
  2. Identify loops that halve or double the variable: those are logarithmic.
  3. Add sequential parts, multiply nested parts, drop constants.
  4. 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 →