What you'll learn
Quick Answer
Big O describes how the running time of an algorithm grows as the input gets bigger, not how many seconds it takes. O(1) means the work stays the same however large the input, O(log n) means it halves each step, O(n) means it grows in step with the input, O(n log n) is the target for good sorting, and O(n squared) means nested loops over the same data. You find the complexity by counting how many times the input is touched, keeping only the fastest-growing term and dropping constants.
What Big O Actually Measures
Big O measures growth, not speed. This is the single most misunderstood point in the whole topic. An O(n squared) algorithm can easily beat an O(n) one on a list of ten items. The question Big O answers is different: what happens when the input gets much larger?
Think about searching for a name in a phone book. If you check every entry from the start, doubling the size of the book doubles your work. If you open it in the middle and repeatedly halve the search, doubling the size adds just one extra step. Both find the name. Only one of them still works when the book has a million entries.
That is why interviewers ask about complexity rather than timing. Timing depends on your laptop, the language, and what else is running. Growth is a property of the algorithm itself, and it is the thing that decides whether your solution survives the largest test case.
Two rules make the notation manageable. First, drop the constants: an algorithm that does 3n operations and one that does n are both O(n), because the shape of the growth is the same. Second, keep only the fastest-growing term: n squared plus n is just O(n squared), because for large n the n squared part completely dominates.
The Complexities You Must Know
Five show up in almost every interview. Learn to recognise them from the shape of the code rather than memorising a table.
O(1) — constant. The work does not depend on the input size at all. Reading arr[5], pushing to a stack, or looking up a key in a hash map are all O(1). There is no loop over the data.
def first_item(arr):
return arr[0] # one step, whether arr has 10 items or 10 millionO(log n) — logarithmic. Each step throws away half the remaining data. Binary search is the classic case. Doubling the input adds only one extra step, which is why log n is so close to constant in practice: a million items need about twenty steps.
O(n) — linear. One pass over the input. Finding a maximum, summing a list, or checking whether a value exists in an unsorted array.
def find_max(arr):
best = arr[0]
for x in arr: # touches every element once
if x > best:
best = x
return bestO(n log n) — linearithmic. The best you can do for comparison-based sorting. Merge sort and quicksort (on average) live here. If a problem needs sorting, n log n is usually the target to aim for.
O(n squared) — quadratic. A loop inside a loop over the same data. Comparing every pair of elements. For n = 1000 that is a million operations, which is fine; for n = 100000 it is ten billion, which is not.
def has_duplicate(arr):
for i in range(len(arr)):
for j in range(i + 1, len(arr)): # nested over the same data
if arr[i] == arr[j]:
return True
return FalseHow to Work It Out in an Interview
You do not need calculus. Count how many times the input is traversed, and look at what the loops do to the remaining work.
- No loop over the data means O(1).
- One loop from start to end means O(n). Two loops one after the other are still O(n), because n plus n is 2n and constants are dropped.
- A loop inside a loop, both over the same input, means O(n squared).
- A loop that halves or doubles a counter each step means O(log n). Look for
mid = (low + high) // 2ori *= 2. - Sorting anything costs O(n log n) unless you are told otherwise — and that cost does not disappear because you used a built-in.
The last point catches people out constantly. Writing arr.sort() looks like one line, but it contributes O(n log n) to your total. If your solution is a sort followed by a single pass, the honest answer is O(n log n), not O(n), because the sort dominates.
Nested loops over different inputs are also not automatically n squared. Looping over an array of size n inside a loop over an array of size m is O(n times m). Say that rather than guessing.
Space Complexity Counts Too
Interviewers usually ask for both, and candidates usually forget the second. Space complexity measures the extra memory your algorithm needs as the input grows — not the input itself.
Reversing an array by swapping ends inward uses O(1) extra space: a couple of index variables, regardless of size. Building a reversed copy uses O(n), because the new array grows with the input.
Recursion has a hidden space cost that trips people up. Each pending call sits on the call stack, so a recursive function that goes n levels deep uses O(n) space even if it allocates nothing itself. That is exactly why deep recursion causes a stack overflow while the equivalent loop runs happily.
The usual trade is time against space. A hash map turns an O(n squared) pair-finding problem into O(n) time — but costs O(n) memory to hold the map. Being able to state that trade out loud is worth as much as the answer itself.
Best, Average and Worst Case
Big O usually refers to the worst case, because that is the guarantee you can rely on. But the distinction matters for some famous algorithms, and interviewers probe it.
Quicksort is the standard example. On average it is O(n log n), which is why it is used everywhere. Its worst case is O(n squared), which happens when the pivot is consistently the smallest or largest element — for instance running naive quicksort on an already-sorted array. Merge sort is O(n log n) in every case, which is why it is preferred when predictable behaviour matters more than raw average speed.
Linear search is O(1) at best (the item is first) and O(n) at worst (it is last or absent). Quoting the best case as the complexity is a mistake: it describes luck, not the algorithm.
Hash map lookup is the other case worth knowing. It is O(1) on average, but O(n) in the worst case when every key collides into the same bucket. In practice you say O(1), and mentioning that you know why it can degrade signals real understanding.