Big O Notation —
How fast "fast enough" actually is.
Big O describes how an algorithm's cost grows as input size grows — not the exact runtime, just the shape of the growth curve. It's the language every interview complexity question is asked in. Watch operation counts for O(1), O(n), and O(n²) code run on the same input on LearnBug and see the gap widen with your own eyes.
What does Big O actually measure?
Big O describes the rate of growth of an algorithm's cost as input size (n) increases — not a precise runtime in seconds, which would depend on hardware. O(n) means "cost grows proportionally with n"; O(n²) means "cost grows proportionally with n squared." It's a shape, not a stopwatch reading.
Why visualization helps
Everyone can recite "O(n²) is worse than O(n)," but the gap doesn't feel real until you watch operation counts diverge on actual input. LearnBug can run O(1), O(n), and O(n²) versions of code side by side and count real operations, so the abstract growth curve becomes a number you watch increase.
From best to worst, roughly what you'll see in interviews
O(1) and O(log n)
Constant time (array index, hash lookup) and logarithmic time (binary search) — cost barely grows even as n gets huge.
O(n) and O(n log n)
Linear time (a single pass through the input) and linearithmic time (efficient sorting) — the sweet spot most interview answers should land in.
O(n²) and O(2ⁿ)
Quadratic (nested loops over the same input) and exponential (naive recursion with overlapping subproblems) — usually the "can we do better?" follow-up target.
Interview questions about Big O
What's the difference between O(n) and O(n²) in practical terms?
For n=1,000, O(n) does about 1,000 operations; O(n²) does about 1,000,000 — a thousand times more work for the same input size. That gap only grows as n increases, which is exactly why interviewers care about it even when both approaches "work" on small test cases.
Why do we ignore constant factors in Big O?
Because Big O describes growth rate, not exact speed — an algorithm that does 2n operations and one that does 100n operations are both O(n), since they scale identically as n grows, even though one is literally 50× slower at every input size. Big O answers "how does this scale," not "which is faster right now."
What's the difference between best, average, and worst case?
Best case is the friendliest possible input (already-sorted array for insertion sort); worst case is the most adversarial (reverse-sorted for quick sort with a naive pivot); average case is the expected cost over typical/random input. Interviews usually care about worst case unless you're explicitly asked about average behavior.
How do I identify an algorithm's Big O just by reading the code?
Count nested loops over the input — one loop is usually O(n), a loop inside a loop is usually O(n²). Recursive calls that split the input in half each time and do O(n) work at each level often give O(n log n). See Time Complexity Explained for the full walkthrough of this process.
Is O(1) always the goal?
No — O(1) means constant time, but some problems inherently require looking at every element at least once (like finding the maximum in an unsorted array), which makes O(n) the best possible complexity for that specific problem. The goal is the best complexity achievable for the problem, not always the fastest complexity class in the abstract.
What does "amortized" complexity mean?
It's the average cost per operation over a sequence of operations, even if individual operations occasionally cost more. Python's list .append() is amortized O(1) — most calls are truly O(1), but occasionally the list must resize and copy everything (O(n)), averaging out to O(1) per call over many appends.
Three complexities on the same input
def constant_time(arr):
return arr[0] # O(1) — always exactly 1 step
def linear_time(arr):
total = 0
for x in arr: # O(n) — n steps
total += x
return total
def quadratic_time(arr):
pairs = 0
for i in arr: # O(n²) — n * n steps
for j in arr:
pairs += 1
return pairs
data = [1, 2, 3, 4, 5]
print(constant_time(data)) # 1 operation, always
print(linear_time(data)) # 5 operations
print(quadratic_time(data)) # 25 operationsQuick Reference
Watch the operation counts diverge with your own eyes
Paste O(1), O(n), and O(n²) code into LearnBug and compare execution directly.