🧠 Data Structures & Algorithms · Advanced

Big-O notation in Java

O(1), O(log n), O(n), O(n log n), O(n²); time vs space.

🧩 The mysteryTwo programs both handle 1,000 users in a blink. At a million users, one still takes a blink and the other takes days. Big-O tells you which is which before you ship.

Growth, not speed

Big-O describes how running time (or memory) grows as the input size n grows. It ignores your CPU and constant factors: O(2n + 5) is just O(n), because the constants and smaller terms stop mattering as n gets big. It's how a commute grows with distance, not how fast your car is today.

The five shapes

From slowest-growing to fastest: O(1) constant, like a typical HashMap.get. O(log n) halving, like binary search. O(n) one pass, like summing an array. O(n log n) good sorting. O(n²) comparing every pair, usually nested loops over n.

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

🔮 Predict it

Halving

How many times does the loop body run?

int n = 64, steps = 0;
for (int i = n; i > 1; i /= 2) steps++;
System.out.println(steps);

6
32
64
7

Show the answer

Round by round, i goes 64, 32, 16, 8, 4, 2, then stops at 1: 6 halvings, which is log2 64. Double n to 128 and you add just one more round. That's O(log n).

🔮 Predict it

Doubling outer, full inner

What does this print?

int n = 16, count = 0;
for (int i = 1; i < n; i *= 2)
    for (int j = 0; j < n; j++) count++;
System.out.println(count);

64
256
16
32

Show the answer

The outer loop runs for i = 1, 2, 4, 8: 4 times (log2 16). The inner loop runs 16 times each: 4 x 16 = 64. Log n rounds of n work is the shape of O(n log n). A full n x n nest would be 256.

⚠️ The trap

Big-O isn't a stopwatch

An O(n) algorithm is not always faster than an O(n²) one. Big-O describes growth; for small n, constant factors win. That's why library sorts switch to O(n²) insertion sort for tiny ranges: it's faster there.

Space is measured separately

Space complexity uses the same notation for the extra memory an algorithm needs. This method's time is O(n), and it also allocates a new array of n + 1 ints, so its extra space is O(n). Using only a few variables would be O(1) space.

int[] prefix(int[] a) {
    int[] p = new int[a.length + 1];
    for (int i = 0; i < a.length; i++)
        p[i + 1] = p[i] + a[i];
    return p;
}

💼 In the real world

Why engineers care

A nested loop over 100,000 users is 10 billion steps; a HashMap lookup per user is 100,000. Spotting these shapes at a glance is how you catch performance bugs in code review, and every technical interview asks for the Big-O of your solution.

Key takeaways

Drop constants and small terms: O(2n + 5) is O(n)
Nested loops over n usually mean O(n²)
Halving the problem each step gives O(log n)
Time and space are measured separately

💡 Big-O is like asking how a commute grows with distance, not how fast your car is today.

🤯 Did you know?

The O comes from German: Paul Bachmann introduced the notation in 1894 for the "order" (Ordnung) of a function, and Edmund Landau later popularized it.

Practice questions

What is the time complexity of this loop?

int steps = 0;
for (int i = n; i > 1; i /= 2) {
    steps++;
}

O(n)
O(n / 2)
O(log n)
O(1)

Check your answer

O(log n). i is halved every iteration, so it reaches 1 after about log₂ n steps. Doubling n adds just one more iteration.

What does this print?

int n = 8, count = 0;
for (int i = 1; i < n; i *= 2) {
    for (int j = 0; j < n; j++) count++;
}
System.out.println(count);

Check your answer

24. The outer loop runs for i = 1, 2, 4 (log₂ 8 = 3 times) and the inner loop runs 8 times each: 3 × 8 = 24. That's the shape of O(n log n).

Next: guess a number from 1 to 100 in at most 7 tries. That trick is binary search.