What is Big O?
Big O notation describes how an algorithm's runtime or memory usage grows as the input size grows. It is not about exact time in milliseconds โ it is about growth rate.
When someone says "this algorithm is O(n)," they mean: if you double the input, the work roughly doubles. If it is O(n squared), doubling the input quadruples the work. That difference matters enormously at scale.
Every coding interview at Google, Microsoft, Amazon, or top startups in Bangalore and Nairobi will ask: "What's the time complexity?" If you cannot answer, your solution is incomplete โ even if it produces the right output. Big O is the shared vocabulary between you and your interviewer.
Common complexities
There are seven complexity classes you will encounter repeatedly. From fastest to slowest:
O(1) โ Constant
The operation takes the same time regardless of input size. Dictionary lookups, array indexing, and hash set membership checks are all O(1). Whether your list has 10 items or 10 million, arr[0] is instant.
O(log n) โ Logarithmic
The algorithm halves the problem each step. Binary search is the classic example. For a sorted array of 1 billion elements, binary search needs at most ~30 comparisons. That is the power of logarithmic time.
O(n) โ Linear
One pass through the data. A single loop that visits every element. Finding the maximum in an unsorted array, summing a list, or checking if an element exists (without a hash set) are all O(n).
O(n log n) โ Linearithmic
The best possible time for comparison-based sorting. Merge sort, heap sort, and Python's built-in sorted() all run in O(n log n). You cannot sort faster than this with comparisons alone.
O(n squared) โ Quadratic
Nested loops over the data. Bubble sort, selection sort, and brute-force duplicate detection. At n=10,000, that is 100 million operations. At n=100,000, it becomes impractical.
O(2 to the n) โ Exponential
The work doubles with each additional input element. Naive recursive fibonacci, generating all subsets. At n=30, you have over a billion operations. At n=50, you wait for hours.
O(n!) โ Factorial
Generating all permutations. At n=12, that is 479 million operations. At n=20, the universe ends before your code finishes. Avoid this at all costs.
Operations count comparison
| Big O | n = 10 | n = 100 | n = 1,000 | n = 10,000 |
|---|---|---|---|---|
| O(1) | 1 | 1 | 1 | 1 |
| O(log n) | 3 | 7 | 10 | 13 |
| O(n) | 10 | 100 | 1,000 | 10,000 |
| O(n log n) | 33 | 664 | 9,966 | 132,877 |
| O(n²) | 100 | 10,000 | 1,000,000 | 100,000,000 |
How to analyze code
Analyzing Big O follows three simple rules:
Rule 1: Drop constants
O(2n) is just O(n). O(100n) is still O(n). Constants do not change the growth rate. Whether you loop through the array once or three times, it is still linear growth.
Rule 2: Drop lower-order terms
O(n squared + n) is just O(n squared). As n gets large, the n squared term dominates completely. The extra n becomes irrelevant.
Rule 3: Focus on worst case
Unless explicitly asked about best or average case, analyze the worst case. What happens when the input is adversarial? That is what Big O captures by default.
Code examples with analysis
Let us walk through four real examples, from constant to quadratic, and see how to optimize.
Space complexity
Space complexity measures the extra memory your algorithm uses โ not counting the input itself. It uses the same Big O notation.
In-place: O(1) space
An algorithm that only uses a fixed number of variables regardless of input size. Swapping two elements, finding a max with a single variable, or reversing an array in place.
Extra space: O(n)
Creating a new array, hash set, or dictionary that grows with the input. The has_duplicate_optimal function above uses O(n) extra space for the seen set.
Best, average, and worst case
Big O typically describes the worst case, but some algorithms have very different behaviors depending on the input.
Best case: O(n log n) โ The pivot splits the array roughly in half each time. Balanced partitions lead to logarithmic depth with linear work at each level.
Average case: O(n log n) โ Random pivots tend to produce reasonably balanced partitions. This is why quick sort is fast in practice.
Worst case: O(n squared) โ The pivot is always the smallest or largest element (e.g., already sorted input with first-element pivot). Each partition only removes one element. This is why production implementations use randomized or median-of-three pivots.
Try It Yourself
Mystery function analysis
Read each mystery function below. Determine its Big O before running the code. Then click Run to see timing data that confirms your analysis.
Task
Given this function, determine its Big O. Then rewrite it to be more efficient.
Hint 1: The brute force is O(n squared) because of the two nested loops.
Hint 2: Use a dictionary to store numbers you have seen. For each number, check if target - num is already in the dict.
Hint 3: One pass through the array with a dict lookup (O(1)) per step gives you O(n) total.
Solution: seen = {} then for each num: if target - num in seen, return the indices. Otherwise seen[num] = i.
Test your knowledge
You can read Big O.
Now master the algorithms.
Join the Best AI Programs โ three 5-month courses, fully online, with placement assistance. Week 1 is free.
Explore our AI-era courses โ