Time and Space Complexity in Java: Big O Notation Explained

Welcome to your first DSA lesson! Before we touch a single data structure, we need a way to answer the most important question in all of algorithms: "is this solution fast enough?" That's what time and space complexity — and the famous Big O notation — are for. Master this idea and every future DSA topic will make more sense. It's the language interviewers speak, so let's make it genuinely clear.

Why not just time it with a stopwatch?

Because the raw time depends on your computer, your mood, and what else is running. We need a way to measure how an algorithm scales — how its work grows as the input gets bigger — independent of hardware. That's exactly what Big O captures: the growth rate, not the literal seconds.

Big O: counting how work grows with input size (n)

Big O notation describes the worst-case number of steps an algorithm takes, as a function of the input size n. We ignore constants and small terms and keep only the dominant factor — because what matters is the shape of the growth. Let's meet the common ones, from best to worst.

O(1) — Constant time

The work is the same no matter how big the input is. Accessing an array element by index is the classic example:

int first = arr[0];   // O(1) — one step, whether arr has 10 or 10 million items

O(n) — Linear time

The work grows in direct proportion to n. A single loop over the input is O(n):

for (int i = 0; i < n; i++) {
    System.out.println(arr[i]);   // n items → n steps → O(n)
}

O(n²) — Quadratic time

Work grows with the square of n — usually a loop inside a loop. Fine for small inputs, but it explodes quickly:

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        // runs n × n = n² times → O(n²)
    }
}

O(log n) — Logarithmic time

Beautifully efficient — the work grows very slowly because each step halves the problem. Binary search is the star example (more in the searching lesson). Doubling the input adds just one extra step.

Comparing the growth

Look at that last row: for a million items, an O(n²) solution does a trillion steps while O(n) does a million. That gap is exactly why interviewers care whether you can turn an O(n²) brute force into something faster.

Space complexity

The same idea applies to memory. Space complexity measures how much extra memory an algorithm uses as n grows. Using a few variables is O(1) space; creating a new array of size n is O(n) space. There's often a trade-off — you can sometimes use more memory to save time, or vice versa.

The rules of thumb for finding Big O

• A simple loop over the input → O(n).
• A loop inside a loop → O(n²).
• Halving the problem each step → O(log n).
• Drop constants: O(2n) is just O(n); O(n + 100) is O(n).
• Keep the biggest term: O(n² + n) is O(n²).

When I started DSA, I treated Big O as annoying interview trivia — until it reframed how I think about every solution. Now the first question I ask myself is "how does this scale?" Interviewers rarely just want a working answer; they want the efficient one, and they'll ask "what's the time complexity?" about everything you write. Get comfortable saying "this is O(n) time, O(1) space" out loud — it's the vocabulary of the entire field, and every lesson from here builds on it.

Key takeaways

• Big O measures how an algorithm's work grows with input size n — the growth rate, not raw seconds.
• Common orders (best→worst): O(1), O(log n), O(n), O(n log n), O(n²).
• A loop is O(n); nested loops are O(n²); halving each step is O(log n).
• Space complexity applies the same idea to extra memory used.

← Back to the DSA roadmap
Next: DSA Lesson 2 — Arrays & Two Pointers →