Big O Notation

Task: Watch how each complexity class grows as the input gets bigger

Why Do We Need Complexity Analysis?

The examples from here to the end of the Complexity section are written in Python rather than the Java used through Fundamentals. Complexity is about the shape of the work, and Python shows that shape with the least syntax in the way. Every conclusion transfers to Java unchanged.

Consider two algorithms that solve the same problem.

One takes a few milliseconds for 100 inputs. Another takes much longer as the input grows.

For small inputs, both may appear fast. But as the input becomes 10,000 or 1,000,000, their difference can become enormous.

We therefore need a way to describe how an algorithm's resource usage grows as the input grows.

That is what complexity analysis gives us.

Complexity analysis helps us evaluate an algorithm without depending on a particular computer, programming language, or exact execution time.

The two resources we mainly care about are:

Time: how the amount of work grows.
Space: how the additional memory requirement grows.

What Is Algorithm Complexity?

Algorithm complexity describes how the resources required by an algorithm change with the size of its input.

We usually represent input size using n.

For example:

An array with 10 elements gives n = 10
An array with 1,000 elements gives n = 1,000
A string containing 50 characters gives n = 50

We are usually not interested in the exact number of milliseconds an algorithm takes.

Instead, we ask:

What happens to the amount of work when n becomes larger?

This distinction is important because the same algorithm can run at different speeds on different machines.

Time Complexity vs Space Complexity

Time complexity describes how the number of operations grows with the input size.

Code

for i in range(n):    print(i)

The loop executes approximately n times. Its time complexity is O(n).

Space complexity describes how the memory required grows with the input size.

Code

result = [] for i in range(n):    result.append(i)

The result list grows with n. Its auxiliary space is O(n).

The two answer different questions, and an algorithm can be cheap in one and expensive in the other.

Complexity	Question
Time	How does the amount of work grow?
Space	How does additional memory usage grow?

Time Complexity and Space Complexity each take one of these apart in full. This chapter is about the notation both of them are written in.

What Does Big O Mean?

Big O notation describes the upper-bound growth rate of an algorithm as the input size becomes large.

In practice, when we say an algorithm is O(n), we are saying its work grows linearly with the size of the input.

Big O focuses on growth, not exact execution time.

For example, suppose an algorithm performs 3n + 5 operations. As n becomes very large, the 3n term dominates the constant 5. So we describe its growth as O(n).

Similarly, 5n² + 10n + 20 is O(n²).

The constants and lower-order terms are omitted when describing asymptotic growth.

This is also why Big O is not a stopwatch. If Algorithm A is O(n) and Algorithm B is O(n²), it does not follow that A always runs faster: for small inputs, constant factors and implementation details can easily decide the race. Big O tells you how the two scale, and for a large enough input the difference in growth overwhelms everything else.

So think of Big O as a growth model, not a measurement.

The Most Important Complexity Classes

You will encounter these constantly throughout DSA:

Complexity	Name	Growth
O(1)	Constant	Does not grow with n
O(log n)	Logarithmic	Grows very slowly
O(n)	Linear	Grows proportionally to n
O(n log n)	Linearithmic	Linear work at each of log n levels
O(n²)	Quadratic	Grows with the square of n
O(n³)	Cubic	Grows with the cube of n
O(2ⁿ)	Exponential	Grows extremely quickly
O(n!)	Factorial	Grows even faster

The important thing is not to memorize this table in isolation. You should learn to recognize these patterns in code, which is what the next chapter is for.

O, Ω and Θ

Big O is one of three. You will meet all of them in a textbook or an exam, and only the first in conversation.

Notation	Bound	Reads as
O(f)	Upper	grows no faster than f
Ω(f)	Lower	grows at least as fast as f
Θ(f)	Both	grows exactly like f

Because O is only an upper bound, O(n²) is a true statement about a linear algorithm. It is also a useless one, so the convention is to always state the tightest upper bound you can — which in practice makes an O almost always a Θ in disguise.

That is why nobody says "this sort is Θ(n log n)" out loud. They say O, and mean the tight bound.

What the Input Size Tells You

Complexity is usually taught as a way to classify an algorithm you already have. It is more useful in the other direction: the size of the input tells you which complexities can possibly work, before you have written anything.

A rough guide, assuming the order of a hundred million simple operations per second:

Input size	What can finish
n ≤ 20	O(2ⁿ), O(n!) — brute force over every subset or ordering
n ≤ 5,000	O(n²) — nested loops over the whole input
n ≤ 1,000,000	O(n log n), O(n) — one sort, or one pass
n beyond that	O(log n), O(1) — you cannot even read it all

Read a problem's constraints first. They usually name the complexity you are expected to hit.

This is how complexity gets used in an interview. A problem that says n ≤ 18 is telling you an exponential answer is acceptable. A problem that says n ≤ 10⁶ is telling you that anything quadratic will time out, so stop trying to make nested loops faster and find a different shape of solution.

Common Complexity Patterns in DSA

You will repeatedly encounter these patterns:

Operation / Pattern	Typical Complexity
Array index access	O(1)
Array traversal	O(n)
Binary Search	O(log n)
Simple nested comparison	O(n²)
Efficient comparison sorting	O(n log n)
Hash table lookup	Average O(1)
Tree traversal	O(n)
Graph traversal	O(V + E)

These are typical complexities, not universal rules. The exact complexity depends on the implementation and assumptions.

Common Mistakes

Thinking O(2n) and O(n) are different complexity classes.

They have the same asymptotic growth. Constants are dropped.

Assuming Big O represents exact execution time.

It describes growth. A faster machine changes the seconds and not the shape.

Ignoring the definition of n.

Always know what the input size represents before analysing anything. For a graph it may be two numbers, V and E, rather than one.

Confusing time complexity with space complexity.

They are separate resources. An algorithm can be O(n²) in time and O(1) in space.

Quick Check

1. Why is 5n² + 10n + 20 written as O(n²)?

2. Is an O(2n) algorithm in a different complexity class from an O(n) one?

3. Algorithm A is O(n) and Algorithm B is O(n²). Will A always finish first?

4. Before analysing any algorithm, what is the first thing you have to establish?

Show answer

As n grows, the 5n² term dominates everything else. Big O keeps only the fastest-growing term and drops constants, so 5n² + 10n + 20 becomes O(n²).
No. O(2n) and O(n) are the same class, because the constant multiplier does not change how the work grows.
No. For small inputs, constant factors and implementation details can make B faster. Big O describes how they scale, not which is quicker on a given input.
What n is. The input size has to be defined before a growth rate means anything.

Quick Recap

Complexity analysis describes how an algorithm's resource usage grows with its input.
n is the size of the input, and it has to be defined before anything else.
Big O describes asymptotic growth, dropping constants and lower-order terms.
The classes run O(1), O(log n), O(n), O(n log n), O(n²), O(n³), O(2ⁿ), O(n!).
Time and space are separate resources, analysed separately.
Big O is a growth model, not a stopwatch.

Where This Leads

You now have the notation. The three chapters that follow are what you write in it:

Code

Time Complexity      ↓How does the amount of work grow? Space Complexity      ↓How does the memory requirement grow? Amortized Analysis      ↓What does a whole sequence of operations cost?

Start with Time Complexity, which turns this notation into something you can read off a loop. Then Space Complexity, and finally Amortized Analysis.

Big O is a way to describe how an algorithm scales as its input grows. The goal is not to count every operation, but to understand the growth of the work and memory the algorithm requires.