Analyzing the Complexity of Loops

Analyzing iterative code means deriving its Big-O by counting how many times its loops run as a function of input size n. The whole skill reduces to a few rules: count one loop’s iterations, multiply nested loops, add sequential loops, and watch for loops that halve or grow the range. Master these and you can read the complexity off almost any function at a glance.

Rule 1: a single loop over n is O(n)

If a loop runs once per element, the work is linear. The body’s constant work (a few operations) doesn’t change the class.

long long sum(const std::vector<int>& a) {
    long long total = 0;
    for (int x : a) total += x; // runs n times -> O(n)
    return total;
}

long sum(int[] a) {
    long total = 0;
    for (int x : a) total += x; // runs n times -> O(n)
    return total;
}

function sum(a) {
  let total = 0;
  for (const x of a) total += x; // runs n times -> O(n)
  return total;
}

def sum_all(a):
    total = 0
    for x in a:      # runs n times -> O(n)
        total += x
    return total

Rule 2: nested loops multiply

A loop inside a loop runs outer × inner times. Two independent loops each over n give O(n²).

long long pairSum(const std::vector<int>& a) {
    long long s = 0;
    for (size_t i = 0; i < a.size(); i++)        // n
        for (size_t j = 0; j < a.size(); j++)    // n
            s += a[i] * a[j];                    // n*n = O(n^2)
    return s;
}

long pairSum(int[] a) {
    long s = 0;
    for (int i = 0; i < a.length; i++)        // n
        for (int j = 0; j < a.length; j++)    // n
            s += (long) a[i] * a[j];          // n*n = O(n^2)
    return s;
}

function pairSum(a) {
  let s = 0;
  for (let i = 0; i < a.length; i++)        // n
    for (let j = 0; j < a.length; j++)      // n
      s += a[i] * a[j];                     // n*n = O(n^2)
  return s;
}

def pair_sum(a):
    s = 0
    for i in range(len(a)):          # n
        for j in range(len(a)):      # n
            s += a[i] * a[j]         # n*n = O(n^2)
    return s

The triangular nested loop is still O(n²)

When the inner loop starts at i, it runs n + (n-1) + ... + 1 = n(n+1)/2 times total. That’s O(n²) — half the work of the full square, but Big-O drops the constant ½.

int countPairs(const std::vector<int>& a) {
    int c = 0;
    for (size_t i = 0; i < a.size(); i++)
        for (size_t j = i + 1; j < a.size(); j++) // ~n*(n-1)/2 total
            c++;
    return c;
}

int countPairs(int[] a) {
    int c = 0;
    for (int i = 0; i < a.length; i++)
        for (int j = i + 1; j < a.length; j++) // ~n*(n-1)/2 total
            c++;
    return c;
}

function countPairs(a) {
  let c = 0;
  for (let i = 0; i < a.length; i++)
    for (let j = i + 1; j < a.length; j++) // ~n*(n-1)/2 total
      c++;
  return c;
}

def count_pairs(a):
    c = 0
    n = len(a)
    for i in range(n):
        for j in range(i + 1, n):  # ~n*(n-1)/2 total
            c += 1
    return c

Rule 3: sequential loops add

Two loops one after the other are O(n) + O(n) = O(n). We keep only the dominant term, so an O(n) loop followed by an O(n²) loop is just O(n²).

Rule 4: a halving loop is O(log n)

If the loop variable is multiplied or divided each step (instead of +1), it reaches the bound in logarithmic steps. Dividing n by 2 repeatedly hits 1 after about log₂ n steps.

int countHalvings(int n) {
    int steps = 0;
    while (n > 1) { n /= 2; steps++; } // O(log n)
    return steps;
}

int countHalvings(int n) {
    int steps = 0;
    while (n > 1) { n /= 2; steps++; } // O(log n)
    return steps;
}

function countHalvings(n) {
  let steps = 0;
  while (n > 1) { n = Math.floor(n / 2); steps++; } // O(log n)
  return steps;
}

def count_halvings(n):
    steps = 0
    while n > 1:      # O(log n)
        n //= 2
        steps += 1
    return steps

A loop that grows a variable toward n (i *= 2 until i >= n) is also O(log n) for the same reason.

Going deeper: A halving loop nested inside a loop over n gives O(n log n) — the complexity of efficient sorting. And distinct inputs multiply separately: looping n times over one array and m times over another (independent sizes) is O(n + m) sequentially or O(n · m) if nested. Don’t collapse separate inputs into a single n.

A worked walkthrough

void mystery(const std::vector<int>& a) {
    int n = a.size();
    for (int i = 0; i < n; i++) { /* A: n */ }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) { /* B: n^2 */ }
    for (int k = 1; k < n; k *= 2) { /* C: log n */ }
}

void mystery(int[] a) {
    int n = a.length;
    for (int i = 0; i < n; i++) { /* A: n */ }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) { /* B: n^2 */ }
    for (int k = 1; k < n; k *= 2) { /* C: log n */ }
}

function mystery(a) {
  const n = a.length;
  for (let i = 0; i < n; i++) { /* A: n */ }
  for (let i = 0; i < n; i++)
    for (let j = 0; j < n; j++) { /* B: n^2 */ }
  for (let k = 1; k < n; k *= 2) { /* C: log n */ }
}

def mystery(a):
    n = len(a)
    for i in range(n):                 # A: n
        pass
    for i in range(n):                 # B: n^2
        for j in range(n):
            pass
    k = 1
    while k < n:                       # C: log n
        k *= 2

Add the parts: n + n² + log n. The dominant term wins, so this is O(n²).

For beginners: When in doubt, count the loops. One loop → O(n). Loop in a loop → O(n²). A loop that multiplies/divides its counter → O(log n). Loops in sequence → add (keep the biggest).

Next steps

Loops are only half the story. For functions that call themselves, you need recurrences and recursion trees — see analyzing recursive code. Keep the complexity cheat sheet nearby, then practice on the complexity exercises.