What is Big-O notation?

Big-O notation describes how the running time or space of an algorithm grows as the input size grows. It gives an upper bound on the growth rate, ignoring constant factors.

What are the most common time complexities?

Common complexities are O(1), O(log n), O(n), O(n log n), O(n²), O(2^n), and O(n!).

What is the difference between Big-O and Big-Theta?

Big-O gives an asymptotic upper bound. Big-Theta gives a tight bound, meaning it bounds the function from above and below asymptotically.

Big-O Complexity Explorer

Pick a complexity class, plug in n, and see how fast it grows. Then compare with real algorithms like sorting, search, or graph traversals.

1. Choose complexity & input size

Complexity

n (input size)

Try 10, 100, 1000…

2. Output

Complexity

—

Estimated steps

—

Growth feeling

—

Example

—

Compare common complexities for the same n

Class	Formula used	Steps @ n	Comment
Click “Compare” to fill the table.

Common algorithms and Big-O

Algorithm	Time	Notes
Linear search	O(n)	Scan one by one.
Binary search	O(log n)	Requires sorted array.
Merge sort	O(n log n)	Optimal general sort.
Bubble sort (worst)	O(n²)	Educational, not optimal.
DFS / BFS	O(V + E)	Graph traversal.
Power set generation	O(2ⁿ)	Exponential blow-up.
TSP exact (brute force)	O(n!)	Factorial complexity.

How to read Big-O

Big-O abstracts away constant factors and lower-order terms. When we say an algorithm is O(n), we mean its running time grows proportionally to the input size. When we say O(n²), doubling n roughly quadruples the work.

Formal definition

A function f(n) is O(g(n)) if there exist positive constants c and n₀ such that for all n ≥ n₀, we have
f(n) ≤ c · g(n).

Why it matters

As data grows, asymptotics dominate implementation details. That’s why interviewers, algorithm designers, and competitive programmers care about Big-O.