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.

๐ŸŽฏ
Interview reality
Why interviewers ask about Big O

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.

Key idea:
Big O measures the worst-case upper bound of growth. We care about what happens when n gets large โ€” not when n is 5.

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
Interview tip:
Memorize this table. When an interviewer asks "can you do better?", they want you to move up one row. O(n squared) to O(n log n). O(n) to O(log n). Know where your solution sits.

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.

analysis_rules.py Applying the rules

Code examples with analysis

Let us walk through four real examples, from constant to quadratic, and see how to optimize.

O(1) โ€” Constant time Array access, dict lookup
10 2
O(n) โ€” Linear time Single pass through array
9
O(n²) โ€” Quadratic time (brute force) Nested loops = danger
False True
O(n) โ€” Linear time (optimized with hash set) Same problem, better complexity
False True
The optimization pattern:
The brute-force duplicate check is O(n squared). By trading space for time (using a hash set), we drop to O(n). This is the most common interview optimization: replace a nested loop with a hash map or hash set.

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.

space_complexity.py O(1) vs O(n) space
[5, 4, 3, 2, 1] [5, 4, 3, 2, 1]
Interview tip:
Always state both time and space complexity. "This solution is O(n) time and O(n) space because of the hash set." Interviewers love hearing both.

Best, average, and worst case

Big O typically describes the worst case, but some algorithms have very different behaviors depending on the input.

๐Ÿ“Š
Classic example
Quick sort's three faces

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.

linear_search_cases.py Best, average, worst
0 5 -1
Default to worst case.
When an interviewer asks "what's the complexity?", give the worst case unless they specifically ask for average or best. It is the safest answer and what Big O formally represents.

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.

(click "Run Code" to execute)
Mini Challenge: Analyze and optimize

Task

Given this function, determine its Big O. Then rewrite it to be more efficient.

challenge.pyWhat's the complexity?

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

Question 1 of 5
What does Big O notation describe?
Question 2 of 5
What is the time complexity of accessing an element by index in an array?
Question 3 of 5
You have a function with O(n squared + 3n + 100). What is its simplified Big O?
Question 4 of 5
How can you optimize a brute-force O(n squared) duplicate finder to O(n)?
Question 5 of 5
What is the worst-case time complexity of Quick Sort?
0
/5
Great work! You understand Big O notation.
Next Lesson
Arrays & Strings
Continue
Africa & India's Best AI Academy
๐Ÿค– AI-first ๐ŸŽ“ Placement Assistance

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 โ†’