SoftwareSideHustles
Concepts

Big O Notation Explained With Real Code Examples

A practical explanation of Big O — what O(1), O(log n), O(n), O(n log n) and O(n²) mean, how to work out the complexity of your own code, and the hidden linear operations that make innocent-looking loops slow.

By Software Side Hustles Editorial Team · Published · Updated · 5 min read

Quick answer: Big O describes how the work an algorithm does grows as its input grows, ignoring constant factors. O(1) is constant regardless of size, O(n) grows in proportion to the input, O(n²) grows with the square of it. It matters because the difference between O(n) and O(n²) is invisible on 100 items and decisive on 1,000,000.

The common complexities

Big ONameExampleOperations for n = 1,000,000
O(1)ConstantRead arr[i], look up a key in a hash map1
O(log n)LogarithmicBinary search in a sorted array~20
O(n)LinearLoop over every item once1,000,000
O(n log n)LinearithmicEfficient sorting (Timsort, merge sort)~20,000,000
O(n²)QuadraticCompare every item with every other item1,000,000,000,000
O(2ⁿ)ExponentialTry every subset; naive recursive Fibonacciastronomically large

At a billion simple operations per second, the O(n log n) column finishes in a fraction of a second. The O(n²) column takes over a quarter of an hour.

O(1): constant time

python
def first(items):
return items[0]
prices = {"apple": 0.5}
prices["apple"] # hash lookup: O(1) on average

The work does not depend on how big items or prices is. "Constant" does not mean "fast" — it means "does not grow".

O(n): linear time

python
def total(items):
s = 0
for x in items:
s += x
return s

One pass, one unit of work per item. Double the input, double the time.

O(n²): quadratic time

python
def has_duplicates(items):
for i in range(len(items)):
for j in range(i + 1, len(items)):
if items[i] == items[j]:
return True
return False

A loop inside a loop over the same data. With a set, the same question becomes O(n):

python
def has_duplicates(items):
return len(set(items)) != len(items)

Trading memory (the set) for time is one of the most common optimisations in practice.

O(log n): logarithmic time

Each step halves the remaining work. Binary search on a sorted list of a million items needs about 20 comparisons, because 2²⁰ ≈ 1,000,000:

python
import bisect
i = bisect.bisect_left(sorted_ids, target)
found = i < len(sorted_ids) and sorted_ids[i] == target

Balanced trees and database B-tree indexes give O(log n) lookups for the same reason — which is why adding the right index turns a slow query into a fast one.

O(n log n): sorting

Comparison-based sorting cannot do better than O(n log n) in general, and the built-in sorts in Python, Java and JavaScript achieve it. If you sort inside a loop, though, you multiply: sorting once per item is O(n² log n).

How to work out the complexity of your code

  1. Count loops over the input. One loop: O(n). Nested loops over the same input: O(n²). Sequential loops: O(n) + O(n) = still O(n).
  2. Drop constants and smaller terms. O(3n + 50) is O(n). O(n² + n) is O(n²).
  3. Use different letters for different inputs. Looping over users and, inside, over orders is O(u × o), not O(n²).
  4. Look inside the loop body for hidden costs. This is where most real-world slowness comes from.

Hidden O(n) operations inside loops

These look like single steps but scan or copy the whole collection:

OperationCostFaster alternative
x in some_list (Python), arr.includes(x) (JS)O(n)use a set / Set: O(1)
list.pop(0), list.insert(0, x) (Python)O(n)collections.deque: O(1) at both ends
arr.shift() / arr.unshift() (JS)O(n)index pointer, or a proper queue
ArrayList.remove(0) (Java)O(n)ArrayDeque
LinkedList.get(i) (Java)O(n)ArrayList for random access
s = s + piece in a loop (Python, Java)O(n) copy per step"".join(parts), StringBuilder
arr.indexOf(x) / list.index(x)O(n)a dict/map from value to index
A database query inside a loop (N+1 queries)n round tripsone query with JOIN or IN

A loop of n iterations containing any of these is O(n²) — even though there is only one visible loop.

Space complexity

Big O also describes memory. Building a set of all items is O(n) extra space; reversing an array in place with two pointers is O(1) extra space. Recursion uses stack space proportional to its depth, which is how stack overflow errors happen.

Average, worst case and amortised

  • Hash maps are O(1) on average, but O(n) in the worst case when many keys collide. Real implementations make that worst case very unlikely.
  • Appending to a dynamic array (list.append, ArrayList.add, arr.push) is amortised O(1): occasionally the array has to grow and copy everything, but averaged over many appends each costs a constant amount.
  • Quicksort is O(n log n) on average and O(n²) in the worst case, which is why libraries use variants or other algorithms with better guarantees.

When Big O does not matter

For small inputs, constants dominate: a simple O(n²) loop over 20 items can beat a clever O(n log n) algorithm with more overhead. Readability matters too. Optimise when the input can be large or the code runs often — and measure with a profiler, not guesses.

Frequently asked questions

What is the difference between Big O, Big Theta and Big Omega?

Strictly, Big O is an upper bound, Omega a lower bound and Theta a tight bound. In everyday engineering conversation, "Big O" is used to mean the tight bound for the case being discussed.

Is O(2n) the same as O(n)?

Yes. Constant factors are dropped because they do not change how the cost grows.

What is the Big O of a dictionary lookup?

O(1) on average for hash-based dictionaries (Python dict, JavaScript Map, Java HashMap). Tree-based maps such as Java's TreeMap are O(log n).

How do I improve an O(n²) algorithm?

Usually by precomputing a lookup structure (a set or map), sorting first so you can use two pointers or binary search, or reducing repeated work with caching.

Where this skill pays off

Complexity analysis is one of the main criteria for judging AI-generated solutions — is the "clever" answer actually faster, and does the stated complexity match the code? Try our free linear vs binary search and nested-loop exercises, and read what makes one coding solution better than another.

Cookies on this site

We use essential cookies to run the questionnaire, practice labs and sign-in. With your permission we'd also like to use analytics to understand which pages help people, and advertising cookies to measure our Google Ads. Rejecting never limits any feature. Cookie policy