Lesson 1.1 · Big-O and Complexity

What Big-O Measures

Big-O counts how the number of steps grows with the input size, ignoring constants and small terms, so you can compare algorithms without a stopwatch.

15 min

Think of it like this

Imagine finding a friend's name on a guest list. Reading every name (O(n)) takes twice as long when the list doubles. Looking it up in an alphabetical list by opening the middle and halving (O(log n)) takes only one extra step when the list doubles. Big-O describes that growth, not the exact seconds.

1.Count the steps, not the seconds

Seconds depend on the computer, the language and what else is running. Steps depend only on the algorithm. So we count how many basic steps (a comparison, an addition, an array read) the code does for an input of size n.

Then we keep only the part that grows fastest and drop constant factors. 3n + 5 steps is O(n); n²/2 + 10n is O(n²). For big inputs, the biggest term decides everything.

2.Reading code for its Big-O

One loop over the input: O(n). A loop inside a loop, both over the input: O(n²). A loop that halves its range each time: O(log n), because you can only halve n about log₂ n times before reaching 1. Steps that don't depend on n (a few assignments): O(1).

Loops one after another add up (O(n) + O(n) = O(n)); loops inside each other multiply (O(n) × O(n) = O(n²)).

CountSteps.java

public class Main {
    public static void main(String[] args) {
        int n = 1024;
        long single = 0, nested = 0, halving = 0;

        for (int i = 0; i < n; i++) single++;                    // O(n)

        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) nested++;                // O(n^2)

        for (int size = n; size > 1; size /= 2) halving++;       // O(log n)

        System.out.println("n=" + n + " single=" + single + " nested=" + nested + " halving=" + halving);
    }
}

Output

n=1024 single=1024 nested=1048576 halving=10

Quick check

What is the Big-O of for (i = 0; i < n; i++) for (j = i; j < n; j++) work();?

3.Big-O, Big-Θ and Big-Ω

Strictly, Big-O is an upper bound ("grows no faster than"), Big-Ω is a lower bound ("grows at least as fast as") and Big-Θ is a tight bound (both). In interviews, people say "Big-O" and mean the tight bound for the worst case, and that's how this course uses it.

Some algorithms behave differently on lucky inputs: linear search finds the target at index 0 in one step (best case) but may need n steps (worst case). Unless told otherwise, give the worst case.

Remember

Big-O describes growth: how work increases as n increases.
Keep the fastest-growing term and drop constants.
Sequential loops add; nested loops multiply; halving gives log n.
Quote the worst case unless asked otherwise.

Common mistakes

Saying O(2n) or O(n/2) instead of O(n).
Calling two separate loops O(n²).
Ignoring the cost of library calls inside a loop (a list.contains inside a loop is O(n) per call).

Words used in this lesson

n: The size of the input, such as the length of the array.
Big-O: An upper bound on how fast the work grows with n.
log n: How many times you can halve n before reaching 1 (about 17 for 100,000).
Worst case: The input that makes the algorithm do the most work.

Command Palette

What Big-O Measures

1.Count the steps, not the seconds

2.Reading code for its Big-O

3.Big-O, Big-Θ and Big-Ω