Complexity analysis: Big-O, Ω, Θ

The first question of a data structures course is always the same: how fast is this code? We don’t measure in seconds, because seconds change from computer to computer. Instead, we look at how the number of operations grows as the input size n grows. On the exam you are given a piece of code and asked “What is the time complexity?”. The answer is one line, but its justification depends on counting the loops correctly.

Golden rules:

1. Drop constants. 3n and n are in the same class: O(n).
2. Keep the dominant term. For n² + 1000n the answer is O(n²).
3. Sequential loops add, nested loops multiply.
4. If a counter doubles or halves, the number of rounds is log n.
5. Look at the bound of the inner loop. If it does not depend on n, the inner loop is constant.

Algorithm and running time

An algorithm is a finite sequence of steps that solves a problem. A data structure is how data is organized in memory: array, linked list, stack, queue. You can solve the same problem with different data structures, and the speed can differ a lot. Throughout this course, for each structure we will ask “how many steps for insertion, how many for deletion, how many for search”.

We write the running time as a function of n: T(n). Consider this method that adds up the elements of an array:

int sum = 0;                    // 1 operation
for (int i = 0; i < n; i++) {   // 1 comparison per round
    sum += a[i];                // 1 addition per round
}
return sum;                     // 1 operation

Roughly T(n) = 2n + 2 operations. 22 for n = 10, 202 for n = 100. The exact number doesn’t matter here. What matters: when n grows ten times, the work grows about ten times. This is linear growth and is written O(n).

Big-O, Big-Omega, Big-Theta

There are three notations, and all three answer the question “how fast does the function grow for large n”.

Formal definition: if there exist a constant $c > 0$ and an $n_0$ such that $T(n) \le c \cdot f(n)$ for every $n \ge n_0$, then $T(n) = O(f(n))$.

Example: $T(n) = 3n + 5$. If you choose $c = 4$, $n_0 = 5$, then $3n + 5 \le 4n$ for $n \ge 5$. So $T(n) = O(n)$. Since $3n + 5 \ge 3n$ it is also $\Omega(n)$, and since both hold, $\Theta(n)$.

PITFALL · Big-O is only an upper bound. The statement $3n + 5 = O(n^2)$ is also mathematically true, because n² grows faster. But on the exam the “tightest bound” is asked for. Your answer should be O(n).

In practice, exams ask for Big-O and expect the tightest answer. You can think of it as writing the same thing as Big-Theta.

Best, worst and average case

For some algorithms the time also depends on the contents of the input. When doing linear search in an array, if the element you are looking for is first, 1 comparison is enough (best case, O(1)). If it is not there at all, n comparisons are needed (worst case, O(n)). Unless stated otherwise, Big-O is given for the worst case.

Common growth rates

Order: $1 < \log n < \sqrt{n} < n < n\log n < n^2 < n^3 < 2^n < n!$

In computer science, if the base of the log is not stated, it is 2. Inside Big-O the base doesn’t matter, because between $\log_2 n$ and $\log_{10} n$ there is only a constant factor.

TIP · Time estimation. For the question “an O(n²) algorithm takes 2 seconds for n = 1000, how long for n = 4000?” use the ratio: n 4 times → time 4² = 16 times → 32 seconds. If it were O(n) it would be 4 times (8 seconds), and if O(n³) it would be 64 times.

Counting operations in loops

This is the real topic of the exam. For each loop ask “how many times does it run?”, then combine.

A single loop

for (int i = 0; i < n; i++)      // n rounds → O(n)
    count++;

for (int i = 0; i < n; i += 3)   // n/3 rounds → still O(n)
    count++;

As long as the step size is constant (1, 2, 3…), the loop is linear.

Multiplying / dividing loop

for (int i = 1; i < n; i *= 2)   // 1, 2, 4, 8, ... → log n rounds
    count++;

How many times do you double before you pass n? If $2^k \ge n$ then $k = \log_2 n$. The same holds for a loop going down with i /= 2. For n = 16, i: 16, 8, 4, 2, 1. Five rounds, that is $\log_2 16 + 1$.

Verifying with a counter (n doubles):

i *= 2 loop:   n=1000 → 10 rounds   n=2000 → 11   n=4000 → 12   n=8000 → 13

When n doubles, only one round is added. This is the mark of logarithmic growth.

Nested loops

for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        count++;                 // n · n = n² → O(n²)

If the bound of the inner loop depends on the variable of the outer loop, write out the sum:

for (int i = 0; i < n; i++)
    for (int j = 0; j < i; j++)
        count++;

i = 0 → inner loop 0 times
i = 1 → 1 time
i = 2 → 2 times
...
i = n-1 → n-1 times
Total = 0 + 1 + ... + (n-1) = n(n-1)/2
n = 10 → 45

$\frac{n(n-1)}{2} = \frac{n^2}{2} - \frac{n}{2}$. The dominant term is $\frac{n^2}{2}$, drop the constant: O(n²). It does half the work but the class doesn’t change.

Mixed: linear × logarithmic

for (int i = 0; i < n; i++)          // n times
    for (int j = 1; j < n; j *= 2)   // log n times each time
        count++;

The total is n log n. Counter results:

n=1000 → 10000   n=2000 → 22000 (x2.20)   n=4000 → 48000 (x2.18)   n=8000 → 104000 (x2.17)

If it were O(n) the ratio would be exactly 2, and if it were O(n²) it would be 4. Slightly above 2: n log n.

Sequential loops

for (int i = 0; i < n; i++) count++;        // n
for (int j = 0; j < n * n; j++) count++;    // n²

The total is $n + n^2$, the dominant term is n²: O(n²). They are added, not multiplied.

A dependent but logarithmic outer loop

A hard example: the outer loop doubles, and the inner loop runs i times.

for (int i = 1; i <= n; i *= 2)
    for (int j = 0; j < i; j++)
        count++;

The inner loop runs 1, 2, 4, …, n times in turn. The total is $1 + 2 + 4 + \dots + n = 2n - 1$. So O(n). 31 rounds for n = 16, 2047 rounds for n = 1024. Don’t answer by reflex “there are two loops, so it’s n log n”; add them up.

A step-by-step solution pattern

On the exam, do this for every piece of code:

1. How many times does the innermost statement run? Write the number of rounds for each loop.
2. If nested, multiply the numbers of rounds (if the inner loop depends on the outer one, expand the sum).
3. If sequential, add.
4. Take the dominant term, drop the constants.
5. If you are not sure, count by hand for n = 8 or n = 16, then double n and check the ratio.

The fifth step is a lifesaver. If you find a result like n = 8 → 24 operations, n = 16 → 64 operations, the ratio is about 2.7, which points to n log n (8·3 = 24, 16·4 = 64).

Common mistakes

int count = 0;
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        count++;

int count = 0;
for (int i = 1; i < n; i *= 2)
    count++;

for (int i = 0; i < n; i++)
    for (int j = 0; j < i; j++)
        count++;

for (int i = n; i > 0; i /= 2)
    count++;

for (int i = 0; i < n; i++)
    for (int j = 1; j < n; j *= 2)
        count++;

for (int i = 0; i < n; i++)
    count++;
for (int j = 0; j < n * n; j++)
    count++;

for (int i = 0; i < n; i++)
    for (int j = 0; j < 5; j++)
        count++;

for (int i = 1; i * i <= n; i++)
    count++;

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j += i)
        count++;