Time Complexity Analysis of Algorithms: Big-O, Recurrences, and Worked Examples for GATE and Interviews

You can write code, yet freeze when a GATE question or an interviewer asks, "What is its time complexity?" Memorising that binary search is O(log n) is not the same as being able to count it: on 1000 sorted elements the count is floor(log2 1000) + 1 = 10 comparisons, and the same counting works on a plain loop, a nested loop, and a recurrence. The notation is not the hard part; producing the count under exam time is.

Counting operations: where the dominant term comes from

Time complexity counts elementary operations as a function of input size n, not seconds. A faster machine may reduce a constant factor, but it cannot turn quadratic growth into linear growth.

Suppose an algorithm performs 3n^2 + 5n + 7 operations. At n = 10, the quadratic term contributes 3 x 10^2 = 300 out of 300 + 50 + 7 = 357. At n = 1000, it contributes 3,000,000 out of 3,000,000 + 5,000 + 7 = 3,005,007. Lower-order terms become noise, so the dominant growth is n^2.

Keep this ladder in mind:

1 < log n < sqrt(n) < n < n log n < n^2 < n^3 < 2^n < n!

Logarithm bases do not affect asymptotic complexity because changing the base only multiplies by a constant factor. That ladder and the formal definitions behind it are stated as a standalone reference in Time complexity and asymptotic notation. Here the same bounds fall out of actual counts: six iterations at n = 64, 55 operations at n = 10, and 24 units of merge work at n = 8.

Proving a Theta bound: Big-O, Big-Omega, and the constants

For sufficiently large n and positive constants:

• f(n) = O(g(n)) means f(n) <= c g(n). It grows no faster than g(n) up to a constant factor.

• f(n) = Omega(g(n)) means f(n) >= c g(n). It grows at least as fast as g(n).

• f(n) = Theta(g(n)) means both bounds hold. It grows at the same asymptotic rate as g(n).

To verify that f(n) = 3n^2 + 5n + 7 is Theta(n^2), take any n >= 1:

3n^2 <= 3n^2 + 5n + 7,

so the lower bound works with c1 = 3. Also, because 5n <= 5n^2 and 7 <= 7n^2 when n >= 1,

3n^2 + 5n + 7 <= 3n^2 + 5n^2 + 7n^2 = 15n^2.

The upper bound works with c2 = 15 and n0 = 1. Both bounds hold, so f(n) = Theta(n^2).

Do not equate Big-O with worst case or Big-Omega with best case. Cases select the input-dependent function. Notation bounds that function.

Reading loops through four common patterns

A loop from 1 to n with constant work in its body runs n times, so it is Theta(n).

For a doubling loop, start with i = 1 and multiply i by 2 while i < n. At n = 64, the body runs with i = 1, 2, 4, 8, 16, 32, then stops when i becomes 64. That is exactly six iterations, and log2(64) = 6, so the loop is Theta(log n). By contrast, i = i + 2 still takes a linear number of steps.

When a nested loop's inner bound is i, the total is a sum. At n = 10:

1 + 2 + 3 + ... + 10 = 10 x 11 / 2 = 55.

The general count is n(n + 1)/2, so it is Theta(n^2), although 55 is less than a full 10 x 10 grid's 100 operations.

An outer Theta(n) loop containing an independent doubling loop gives Theta(n log n). Multiply nested independent counts. Add sequential counts and keep the dominant term.

Merge sort's recursion tree, then the Master theorem cases

Divide-and-conquer work forms recurrences. Merge sort gives T(n) = 2T(n/2) + n: two half-sized calls plus linear merging.

For n = 8, the recursion tree is concrete:

• Level 0 has one problem of size 8, contributing 8 units of merge work.

• Level 1 has two problems of size 4, contributing 2 x 4 = 8.

• Level 2 has four problems of size 2, contributing 4 x 2 = 8.

There are log2(8) = 3 merge levels. Their work is 8 + 8 + 8 = 24, or 8 log2(8). Eight constant-work leaves add Theta(n), so the recurrence is Theta(n log n).

For T(n) = aT(n/b) + f(n), compare f(n) with n^(log_b a):

1. If f(n) = O(n^(log_b a - epsilon)) for some epsilon > 0, then T(n) = Theta(n^(log_b a)).

2. If f(n) = Theta(n^(log_b a) log^k n) for k >= 0, then T(n) = Theta(n^(log_b a) log^(k + 1) n).

3. If f(n) = Omega(n^(log_b a + epsilon)) and satisfies a f(n/b) <= c f(n) for some c < 1, then T(n) = Theta(f(n)).

For T(n) = 8T(n/2) + n^2, n^(log_2 8) = n^3 while f(n) = n^2 is polynomially smaller, so Case 1 gives Theta(n^3) and the leaves dominate. Case 3 is the one carrying a side condition. For T(n) = 2T(n/2) + n^2, n^(log_2 2) = n and f(n) = n^2 is larger by a factor of n, so the epsilon test passes with epsilon = 1. The regularity check is a f(n/b) = 2 (n/2)^2 = n^2 / 2, which is at most c f(n) with c = 1/2, and 1/2 is less than 1. Case 3 therefore gives Theta(n^2).

The theorem does not cover every divide-and-conquer recurrence. For T(n) = 2T(n/2) + n/log n, f(n) falls into the gap between the first two cases: it is not polynomially smaller than n, and it is not n log^k n for any k >= 0. No case applies, and expanding the tree by hand gives Theta(n log log n).

Best, average, and worst case counted on 10 and 1000 elements

In linear search over 10 elements, the best case takes one comparison when the first element matches. The worst case takes 10 comparisons when the last element matches or the target is absent. If a present target is equally likely to occupy any position, the average is (1 + 10)/2 = 5.5 comparisons.

For binary search over 1000 sorted elements, the worst-case count is floor(log2 1000) + 1 = 9 + 1 = 10 comparisons. Linear search may need 1000 because it does not halve the remaining search space.

Quick sort shows the case split. Balanced partitions give average Theta(n log n). On sorted input with the last element as pivot, each partition is 0 versus n - 1, producing worst-case Theta(n^2).

Time complexity traps that cost marks

O(n^2) does not mean an algorithm takes exactly n^2 operations. It is an upper bound, so a linear function is also technically O(n^2). Theta is the honest tight statement when both bounds are known.

Likewise, "every O(n log n) algorithm is slower than every O(n) algorithm" is false. Big-O supplies no lower bound, and constants and input ranges affect actual time.

Watch the code rather than its shape. An inner loop with a fixed bound of 100 keeps an outer linear loop at Theta(n). A counter increasing by 2 is still linear. If both a counter and its bound change, count the actual values.

For recurrences, never drop the non-recursive work. Unrolling T(n) = T(n - 1) + n adds n + (n - 1) + ... + 1, giving Theta(n^2). The recurrence T(n) = T(n - 1) + 1 is not Master theorem territory because the problem does not shrink geometrically. It unrolls directly to Theta(n).

How GATE and interviews test time complexity

GATE questions ask you to analyse loops, solve recurrences, order functions, judge notation statements, or calculate an exact count such as the 55 above. The syllabus wording and paper structure for your cycle are published by the organising institute on the official GATE website.

In interviews, give a short counting argument: "The outer loop runs n times, the inner value doubles, so the total is n log n." Also name the input that triggers the worst case, such as sorted input with a naive quick-sort pivot.

Use the GATE Test Series, Mocks and Topic-wise Tests for timed practice. Practise the same reasoning on arrays, stacks, queues, trees, and graphs with Data Structures MCQs.

The short version, and what to drill next

• Count operations as a function of n, not seconds.

• Keep the dominant term, and use Theta for a tight bound.

• Doubling or halving usually creates a logarithm; adding a constant does not.

• Dependent loops often require a sum such as n(n + 1)/2.

• Draw a recursion tree before reaching for a theorem.

• Best, average, and worst case describe inputs. Big-O, Big-Omega, and Theta describe bounds.

GATE Guidance by Sanchit Sir places algorithm analysis inside the full CS preparation sequence rather than teaching it as a standalone topic. If you are mapping the rest of the syllabus, the GATE CS exam preparation courses and test series page lists what each subject needs.