Time Complexity — Practice Set

Instructions for the
Reader

Below you will find seventeen short programs, arranged in four levels of difficulty. For each one, your task is to determine the worst-case time complexity in Big-O notation.

Read carefully. Count the loops. Watch what changes — and how quickly — between iterations. Recursive functions ask you to think in terms of recurrence relations: T(n) = aT(n/b) + f(n).

Resist the temptation to peek. Form your answer first; only then click Reveal.

Level I

i.Foundations

Begin here. Single statements, single loops, simple nesting — the alphabet of analysis.

P. 01The lone statement

C-like

int sum(int a, int b) {
  int result = a + b;
  return result;
}

O(1)

Constant time. The function performs a fixed number of operations regardless of the size of the inputs. No loops, no recursion — the cost is bounded by a constant.

P. 02A single sweep

C-like

int total(int arr[], int n) {
  int sum = 0;
  for (int i = 0; i < n; i++) {
    sum += arr[i];
  }
  return sum;
}

O(n)

Linear time. The loop runs exactly n times, doing constant work in each iteration. Total work is proportional to the size of the input array.

P. 03Loop within a loop

C-like

void printPairs(int n) {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      printf("(%d,%d) ", i, j);
    }
  }
}

O(n²)

Quadratic time. For each of the n iterations of the outer loop, the inner loop runs n times — yielding n × n = n² total operations.

P. 04Constants do not matter

C-like

void process(int arr[], int n) {
  for (int i = 0; i < n; i++) {
    arr[i] *= 2;
  }
  for (int i = 0; i < n; i++) {
    arr[i] += 1;
  }
  for (int i = 0; i < n; i++) {
    printf("%d ", arr[i]);
  }
}

O(n)

Still linear. Three sequential loops give 3n operations — but Big-O drops constant factors. Sequential work adds; it does not multiply.

Level II

ii.Patterns of Growth

Logarithms, triangles, and cubes. The same loop wears many faces, depending on how its index moves.

P. 05Halving the index

C-like

void doubler(int n) {
  for (int i = 1; i < n; i = i * 2) {
    printf("%d ", i);
  }
}

O(log n)

Logarithmic. Because i doubles each iteration, the loop terminates after roughly log₂ n steps. Multiplying (or dividing) the loop variable yields logarithmic behavior.

P. 06The triangle loop

C-like

void upperTriangle(int n) {
  for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
      printf("*");
    }
    printf("\n");
  }
}

O(n²)

Quadratic, even when triangular. The inner loop runs n + (n-1) + (n-2) + … + 1 = n(n+1)/2 times. Dropping constants and lower-order terms, this is O(n²).

P. 07Three deep

C-like

void tripleLoop(int n) {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      for (int k = 0; k < n; k++) {
        printf(".");
      }
    }
  }
}

O(n³)

Cubic. Three nested loops, each running n times, multiply: n × n × n = n³.

P. 08Square root in disguise

C-like

void mystery(int n) {
  int i = 1;
  while (i * i <= n) {
    printf("%d ", i);
    i++;
  }
}

O(√n)

Square-root time. The loop continues while i² ≤ n, i.e., until i ≈ √n. So it runs approximately √n times.

Level III

iii.Mixed Constructs

Now the loops cohabit. An outer linear march paired with an inner logarithmic stride; conditions that bend the bound. Think carefully about what dominates.

P. 09Linear meets logarithmic

C-like

void analyze(int n) {
  for (int i = 0; i < n; i++) {
    for (int j = 1; j < n; j = j * 2) {
      printf("%d %d\n", i, j);
    }
  }
}

O(n log n)

Linearithmic. The outer loop runs n times. For each, the inner loop runs log₂ n times because j doubles. Multiply: n · log n.

P. 10Two paths, one bound

C-like

void twoLoops(int n) {
  // First: nested quadratic
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      printf(".");
    }
  }

  // Then: a single linear sweep
  for (int k = 0; k < n; k++) {
    printf("!");
  }
}

O(n²)

The dominant term wins. Total work is n² + n. Big-O keeps only the fastest-growing term, so the bound is O(n²).

P. 11The harmonic surprise

C-like

void harmonic(int n) {
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j = j + i) {
      printf("*");
    }
  }
}

O(n log n)

The harmonic series in disguise. For each i, the inner loop runs about n/i times. Summing: n/1 + n/2 + … + n/n = n · H_n ≈ n · ln n.

P. 12Conditional cost

C-like

void conditional(int n) {
  for (int i = 0; i < n; i++) {
    if (i % 2 == 0) {
      for (int j = 0; j < n; j++) {
        printf(".");
      }
    } else {
      printf("!");
    }
  }
}

O(n²)

Worst case dominates. Half the iterations cost n work, the other half cost constant. Total: (n/2) · n + (n/2) · 1 = n²/2 + n/2 → O(n²).

Level IV

iv.Recursive Reasoning

Here the function calls itself, and the analysis becomes a recurrence. Write down T(n), then solve.

P. 13The factorial

C-like

int factorial(int n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}

O(n)

Linear recursion. Recurrence: T(n) = T(n-1) + O(1). Each call reduces n by 1, giving a chain of n calls.

P. 14Halve and conquer

C-like

int binarySearch(int arr[], int lo, int hi, int key) {
  if (lo > hi) return -1;
  int mid = (lo + hi) / 2;
  if (arr[mid] == key) return mid;
  if (arr[mid] < key)
    return binarySearch(arr, mid + 1, hi, key);
  else
    return binarySearch(arr, lo, mid - 1, key);
}

O(log n)

Logarithmic divide-and-conquer. Recurrence: T(n) = T(n/2) + O(1). Each call halves the search space, so depth is log₂ n.

P. 15Naive Fibonacci

C-like

int fib(int n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

O(2ⁿ)

Exponential. Recurrence: T(n) = T(n-1) + T(n-2) + O(1). The call tree branches twice at each level, giving roughly 2ⁿ calls (more precisely, O(φⁿ) where φ is the golden ratio).

P. 16Merge sort

C-like

void mergeSort(int arr[], int lo, int hi) {
  if (lo >= hi) return;
  int mid = (lo + hi) / 2;

  mergeSort(arr, lo, mid);          // T(n/2)
  mergeSort(arr, mid + 1, hi);      // T(n/2)
  merge(arr, lo, mid, hi);          // O(n)
}

O(n log n)

Master Theorem, Case 2. Recurrence: T(n) = 2T(n/2) + O(n). With a = 2, b = 2, we have log_ba = 1 and f(n) = n = Θ(n¹), giving T(n) = Θ(n log n).

P. 17The Tower of Hanoi

C-like

void hanoi(int n, char from, char via, char to) {
  if (n == 0) return;
  hanoi(n - 1, from, to, via);
  printf("Move disk %d: %c -> %c\n", n, from, to);
  hanoi(n - 1, via, from, to);
}

O(2ⁿ)

Exponential — and provably so. Recurrence: T(n) = 2T(n-1) + O(1). Solving: T(n) = 2ⁿ - 1. The number of disk moves doubles with each additional disk, which is why this puzzle becomes intractable quickly.