Complexity Analysis and Big-O Notation: A Beginner’s Guide with C++ Examples

Two programs can give the same correct answer and still behave very differently when the data grows. One finishes before you blink, the other makes you wait for minutes. Complexity analysis is the tool we use to tell them apart before we run anything, and Big-O is the language we use to talk about it.

This is Lecture 4 of our Data Structures and Algorithms series. Last time we looked at data structures and abstract data types. Here we learn how to measure how good an algorithm is. All the C++ programs below were compiled and run, and the outputs shown are the real outputs.

Why not just use a stopwatch?

The obvious way to compare two programs is to time them. The problem is that the time depends on things that have nothing to do with the algorithm: how fast your computer is, what else is running, which compiler you used. Your friend with a faster laptop gets a different answer for the same code.

So instead of seconds, we count steps, meaning basic operations such as a comparison or an addition. Steps do not change from machine to machine. What we care about is how the number of steps grows as the input size n grows.

A first example: adding 1 to n

Suppose we want the sum 1 + 2 + 3 + ... + n. There are two ways to do it.

// Way 1: a loop, about n steps
long long sum = 0;
for (int i = 1; i <= n; i++)
    sum += i;

// Way 2: a formula, always one calculation
long long sum = (long long)n * (n + 1) / 2;

For n = 1000 both give 500500 (we checked). But the loop does about 1000 additions, and for n = 1,000,000 it does about a million. The formula does the same single calculation either way. Both are correct, but one is clearly better as n grows. Big-O puts a name on that difference: the loop is O(n), the formula is O(1).

What Big-O actually means

Big-O describes how the number of steps grows when the input grows, and it only keeps the part that matters most. Take an algorithm that takes exactly 3n² + 5n + 2 steps. At n = 1000 that is 3,005,002 steps. The 3n² part alone is 3,000,000, which is about 99.8% of the total. The other terms hardly matter.

So we apply two simple rules:

• Drop the smaller terms. Keep only the fastest-growing one.
• Drop the constant multiplier. 3n² and n² grow in the same way.

That leaves O(n²). Read it as “the work grows roughly with the square of n”.

Common growth rates

Big-O	Name	Typical example
O(1)	Constant	Reading a[5]
O(log n)	Logarithmic	Binary search
O(n)	Linear	One loop over all items
O(n log n)	Linearithmic	Merge sort
O(n²)	Quadratic	Loop inside a loop
O(2ⁿ)	Exponential	Trying every subset

Going left to right is going from “great” to “painful” as n gets large.

Counting steps in real code

Here is a small program that counts the steps of a single loop and of two nested loops.

#include <iostream>
using namespace std;
int main() {
    int n = 10;
    long long steps1 = 0, steps2 = 0;
    for (int i = 1; i <= n; i++) steps1++;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) steps2++;
    cout << "One loop, n=" << n << ": " << steps1 << " steps" << endl;
    cout << "Nested loops, n=" << n << ": " << steps2 << " steps" << endl;
    return 0;
}

Output for n = 10, and then the same program with n = 100:

One loop, n=10: 10 steps
Nested loops, n=10: 100 steps
One loop, n=100: 100 steps
Nested loops, n=100: 10000 steps

When n grew ten times, the single loop grew ten times (10 to 100), but the nested loops grew a hundred times (100 to 10,000). That is the real difference between O(n) and O(n²).

Best, average and worst case

The same algorithm can behave differently depending on the input. Linear search looks through an array one item at a time. We count comparisons.

int linearSearch(int a[], int n, int key, int &comparisons) {
    comparisons = 0;
    for (int i = 0; i < n; i++) {
        comparisons++;
        if (a[i] == key) return i;
    }
    return -1;
}

Running it on the array {7, 3, 9, 1, 5, 8, 2, 6, 4, 10} gives:

best (first item): key 7 -> index 0, comparisons = 1
middle item: key 5 -> index 4, comparisons = 5
worst (last item): key 10 -> index 9, comparisons = 10
not present: key 99 -> index -1, comparisons = 10

• Best case: the key is the first item, 1 comparison, O(1).
• Average case: the key is somewhere in the middle, about n/2 comparisons, still O(n).
• Worst case: the key is last or missing, n comparisons, O(n).

Unless told otherwise, when people quote Big-O they mean the worst case, because it is a promise that the algorithm will never be slower than that.

Big-O, Omega and Theta in one minute

• O (Big-O): an upper bound. “It takes at most this much.”
• Ω (Omega): a lower bound. “It takes at least this much.”
• Θ (Theta): a tight bound. Upper and lower are the same growth rate.

Rules of thumb

Situation	Rule	Result
One block after another	Add, keep the biggest	O(n) then O(n²) gives O(n²)
Loop inside a loop	Multiply	n × n = O(n²)
A single statement	Constant	O(1)
Array access a[i]	Constant	O(1)
Variable is doubled each time	Logarithmic	O(log n)

The doubling loop and O(log n)

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

Here i goes 1, 2, 4, 8, 16... so the loop does not run n times. We ran it: for n = 1000 it takes 10 steps, and for n = 1,000,000 only 20 steps. A million items and just 20 steps. This is why O(log n) algorithms such as binary search are so powerful.

Space complexity

Time is not the only resource. Space complexity counts the extra memory an algorithm needs. A few variables are O(1) extra space. Making a copy of an array with n items is O(n) extra space. Often a faster algorithm uses more memory, and choosing between the two is a design decision.

Common mistakes

• Measuring seconds instead of steps. Seconds change with the machine, steps do not.
• Keeping constants. Writing O(3n²) instead of O(n²).
• Keeping small terms. Writing O(n² + n) instead of O(n²).
• Adding when you should multiply. A loop inside a loop multiplies, two loops one after another add.
• Thinking Big-O is exact. It describes growth, not the precise running time.

Practice: find the Big-O

// (a)
for (int i = 0; i < n; i++) cout << i;

// (b)
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) cout << i + j;

// (c)
for (int i = 1; i < n; i *= 2) cout << i;

// (d)
for (int i = 0; i < n; i++) cout << i;
for (int j = 0; j < n; j++) cout << j;

Show answers

(a) O(n), one loop. (b) O(n²), nested loops. (c) O(log n), i doubles. (d) O(n), two loops one after another: n + n = 2n, and we drop the constant.

Frequently asked questions

What is Big-O notation in simple words?

It is a way to describe how the work of an algorithm grows as the input gets bigger, ignoring small details like constants and minor terms.

Why do we ignore constants in Big-O?

Because for large inputs the growth rate dominates. 3n² and n² both grow quadratically, and that is the information we want.

Which case should I quote, best, average or worst?

Usually the worst case, because it is a guarantee. Mention the average case when it is very different.

Is O(n) always faster than O(n²)?

For large n, yes. For tiny inputs a simple O(n²) method can be just as fast, but Big-O is about what happens as n grows.

Test yourself

Try our 15 practice MCQs on Complexity Analysis and Big-O to check what you learned. Next in the series: linear and binary search, where we put Big-O to work.