Navigation

DSA complexity 9 min read

Complexity Exercises: Answer Sheet & Explanations

This is the answer sheet for the complexity exercises. Each answer gives the result, the reasoning that gets you there, and — where a solution involves code — the implementation in all four languages (use the switcher). Try every question first, then check your reasoning here.

Q1. Single loop

Idea: One loop over n elements with constant work per iteration runs n times. The body’s fixed handful of operations is a constant factor, which Big-O drops.

Complexity: O(n) time, O(1) space.

long long total(const std::vector<int>& a) { // O(n) time, O(1) space
    long long s = 0;
    for (int i = 0; i < (int)a.size(); i++) s += a[i];
    return s;
}

long total(int[] a) { // O(n) time, O(1) space
    long s = 0;
    for (int i = 0; i < a.length; i++) s += a[i];
    return s;
}

function total(a) { // O(n) time, O(1) space
  let s = 0;
  for (let i = 0; i < a.length; i++) s += a[i];
  return s;
}

def total(a):  # O(n) time, O(1) space
    s = 0
    for x in a:
        s += x
    return s

Pitfall: Doing more work per iteration (e.g. 5 operations) does not change the class — it’s still O(n). Big-O ignores constant factors.

Q2. Two sequential loops

Idea: Sequential loops add: O(n) + O(m) = O(n + m). You may only simplify to O(n) when m is known to be the same order as n (or smaller). With two genuinely independent input sizes, collapsing them into one n is wrong — keep both.

Complexity: O(n + m) time, O(1) space.

Pitfall: Writing O(n) when there are two distinct inputs hides real cost. If m can dwarf n (or vice versa), O(n + m) is the only honest answer.

Q3. The doubling loop

Idea: Starting at 1 and doubling until reaching n takes about log₂ n steps, because 2^k ≥ n when k ≥ log₂ n. Any loop that multiplies or divides its counter by a constant factor is logarithmic.

Complexity: O(log n) time, O(1) space.

int doublings(int n) { // O(log n)
    int count = 0;
    for (int i = 1; i < n; i *= 2) count++;
    return count;
}

int doublings(int n) { // O(log n)
    int count = 0;
    for (int i = 1; i < n; i *= 2) count++;
    return count;
}

function doublings(n) { // O(log n)
  let count = 0;
  for (let i = 1; i < n; i *= 2) count++;
  return count;
}

def doublings(n):  # O(log n)
    count = 0
    i = 1
    while i < n:
        i *= 2
        count += 1
    return count

Pitfall: A loop with i += 2 (adding a constant) is still O(n), not O(log n). Only multiplying/dividing the counter gives logarithmic behavior.

Q4. The triangular nested loop

Idea: The inner loop runs n-1, n-2, ..., 1, 0 times across the outer iterations. The sum is n(n-1)/2, which expands to (n² - n)/2. Big-O keeps the dominant term and drops the constant ½, giving O(n²) — there’s no such class as “O(n²/2)” because constants don’t survive.

Complexity: O(n²) time, O(1) space.

int countPairs(const std::vector<int>& a) { // O(n^2)
    int c = 0, n = a.size();
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            c++;
    return c;
}

int countPairs(int[] a) { // O(n^2)
    int c = 0, n = a.length;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            c++;
    return c;
}

function countPairs(a) { // O(n^2)
  let c = 0;
  const n = a.length;
  for (let i = 0; i < n; i++)
    for (let j = i + 1; j < n; j++)
      c++;
  return c;
}

def count_pairs(a):  # O(n^2)
    c = 0
    n = len(a)
    for i in range(n):
        for j in range(i + 1, n):
            c += 1
    return c

Pitfall: Don’t assume “the inner loop is shorter, so it’s O(n)”. Half of a quadratic is still quadratic.

Q5. Misleading nesting

Idea: The outer loop runs n times. Each outer iteration runs an inner loop that halves a value to 1 — that’s O(log n) work. Nested loops multiply, so total is n × log n.

Complexity: O(n log n) time, O(1) space.

int work(int n) { // O(n log n)
    int ops = 0;
    for (int i = 0; i < n; i++) {       // n
        int k = n;
        while (k > 1) { k /= 2; ops++; } // log n each
    }
    return ops;
}

int work(int n) { // O(n log n)
    int ops = 0;
    for (int i = 0; i < n; i++) {       // n
        int k = n;
        while (k > 1) { k /= 2; ops++; } // log n each
    }
    return ops;
}

function work(n) { // O(n log n)
  let ops = 0;
  for (let i = 0; i < n; i++) {                 // n
    let k = n;
    while (k > 1) { k = Math.floor(k / 2); ops++; } // log n each
  }
  return ops;
}

def work(n):  # O(n log n)
    ops = 0
    for _ in range(n):        # n
        k = n
        while k > 1:          # log n each
            k //= 2
            ops += 1
    return ops

Pitfall: A halving loop inside a linear loop is O(n log n), not O(n) — the inner cost repeats n times. This is exactly the shape of efficient sorting.

Q6. Recursive cost

Idea: Two calls on size n-1 give the recurrence T(n) = 2·T(n-1) + O(1). Each level doubles the number of calls, and there are n levels, so the call count is about 2ⁿ. This is the classic exponential blow-up of naive branching recursion (like computing Fibonacci without caching).

Complexity: O(2ⁿ) time, O(n) space (the recursion stack is only n deep at any moment).

long long count(int n) { // T(n) = 2T(n-1)+O(1) -> O(2^n)
    if (n <= 0) return 1;
    return count(n - 1) + count(n - 1);
}

long count(int n) { // T(n) = 2T(n-1)+O(1) -> O(2^n)
    if (n <= 0) return 1;
    return count(n - 1) + count(n - 1);
}

function count(n) { // T(n) = 2T(n-1)+O(1) -> O(2^n)
  if (n <= 0) return 1;
  return count(n - 1) + count(n - 1);
}

def count(n):  # T(n) = 2T(n-1)+O(1) -> O(2^n)
    if n <= 0:
        return 1
    return count(n - 1) + count(n - 1)

Pitfall: Don’t confuse time and space here. Time is exponential (O(2ⁿ) total calls), but space is only O(n) because the stack holds one root-to-leaf path at a time. Memoization can cut the time to O(n) when subproblems repeat.

Q7. Choose the better complexity

Idea: Approach A (compare all pairs) is O(n²) time, O(1) space. Approach B (hash set) is O(n) time, O(n) space — it trades memory to delete the inner loop. Choose B by default: for large n, going from n² to n is a massive win and O(n) extra memory is usually cheap. Choose A only when memory is extremely tight or n is tiny.

Complexity: A: O(n²) time, O(1) space. B: O(n) time, O(n) space.

#include <vector>
#include <unordered_set>
using namespace std;

bool hasDuplicate(const vector<int>& a) { // Approach B: O(n) time, O(n) space
    unordered_set<int> seen;
    for (int x : a) {
        if (seen.count(x)) return true;
        seen.insert(x);
    }
    return false;
}

import java.util.*;

boolean hasDuplicate(int[] a) { // Approach B: O(n) time, O(n) space
    Set<Integer> seen = new HashSet<>();
    for (int x : a)
        if (!seen.add(x)) return true; // add returns false if already present
    return false;
}

function hasDuplicate(a) { // Approach B: O(n) time, O(n) space
  const seen = new Set();
  for (const x of a) {
    if (seen.has(x)) return true;
    seen.add(x);
  }
  return false;
}

def has_duplicate(a):  # Approach B: O(n) time, O(n) space
    seen = set()
    for x in a:
        if x in seen:
            return True
        seen.add(x)
    return False

Pitfall: Always report both axes. “It’s faster” is incomplete — Approach B is faster in time but uses more space. The right answer states the trade-off, not just the winner.

That’s the full answer sheet. Back to the complexity exercises, or continue to arrays.