DSA · Lesson 1 of 9

Big-O & complexity

Measuring how time and memory grow with input size.

Interviewers care less about whether code works on 5 items and more about how it behaves on 5 million. Big-O describes how the number of steps grows as the input size n grows, ignoring constants.

Big-O	Name	Typical example
O(1)	Constant	Read `arr[i]`, dict lookup
O(log n)	Logarithmic	Binary search
O(n)	Linear	One loop over the data
O(n log n)	Linearithmic	Good sorting algorithms
O(n²)	Quadratic	Nested loops over the same data
O(2ⁿ)	Exponential	Trying every subset

Space complexity counts extra memory the same way. Always state both, e.g. “O(n) time, O(1) extra space”.

Try it yourself

Code editor

Press Run to see the output.

Edit and press Run (or Ctrl/⌘ + Enter). Python runs in your browser — the first run downloads the Python engine and takes a few seconds.

Key points

Big-O = growth rate, constants dropped.
Nested loops over n items ≈ O(n²).
A set/dict often turns O(n²) into O(n).

Quick check

What is the time complexity of binary search?

O(1) O(log n) O(n) O(n²)

Practice task

Change the data size to 6000 and compare: the slow version should take roughly 4× longer, the fast one about 2×. Explain why.

Interview corner

What's the complexity of two separate (not nested) loops over n?

O(n) + O(n) = O(2n), which simplifies to O(n).

Is O(n log n) always slower than O(n²)?

No — for large n, O(n log n) grows much more slowly. For tiny inputs constants can dominate, which is why some libraries switch to insertion sort for small arrays.