Discover how to solve Data Structures and Algorithms problems like a strong software engineer—from understanding the problem to optimizing your solution, writing clean code, and analyzing Big-O complexity. Learn through a real-world e-commerce example from Varastra.
Two pieces of code can give the same correct answer. One of them can need more than 100 times more work. Big-O helps you see this before your customers do.
Two pieces of code can give the same correct answer. One of them can need more than 100 times more work. Big-O helps you see this before your customers do.
The problem at Varastra
Varastra is an online store for Indian ethnic wear. Every product page makes about 30 lookups by SKU. A SKU is the code that names one product. The lookups fetch price, stock, sizes and photos.
The catalogue has 50,000 products. Tara, a new intern, writes the lookup code. It works. Her tests pass.
Then Sam, a senior engineer, asks one question: "What happens on sale night?"
Tara runs a test. Finding one SKU in a list of 50,000 takes about 0.37 milliseconds. Finding it in a dict takes about 0.003 milliseconds. A dict is a container that finds an item by its key.
Here is the test she ran.
import time
skus = [f"SKU{i}" for i in range(50_000)]
table = {sku: i for i, sku in enumerate(skus)}
target = skus[-1] # the worst case: the last item
start = time.perf_counter()
for _ in range(100):
target in skus # list: checks items one by one
list_ms = (time.perf_counter() - start) / 100 * 1000
start = time.perf_counter()
for _ in range(100_000):
target in table # dict: jumps straight to the key
dict_ms = (time.perf_counter() - start) / 100_000 * 1000
print(f"list: {list_ms:.4f} ms, dict: {dict_ms:.5f} ms")
Now imagine 500 people open a product page every second. This traffic is made up for the story.
- With the list: about 5.6 seconds of work every second.
- With the dict: about 0.05 seconds of work every second.
The list version falls behind. Pages load slowly and customers leave. Both versions give the right answer. Only the cost is different. These work figures are estimates. They come from the measured lookup times and the made-up traffic.
The diagram at a glance
Big-O is a short way to say how the number of steps grows when the input grows. It ignores the machine. It keeps only the shape.
The diagram shows five shapes for n = 1,000. Here, n is the number of items.
- O(1), constant: 1 step. Read the first item.
- O(log n), logarithmic: 10 steps. Cut the problem in half each time.
- O(n), linear: 1,000 steps. One pass over the data.
- O(n log n), linearithmic: about 10,000 steps. A pass where each item does a halving.
- O(n²), quadratic: 1,000,000 steps. A loop inside a loop.
The bars use a log scale. Each gridline means 10 times more steps than the line before it. So the last bar is not a little longer. It is 1,000 times longer than the O(n) bar.
Here is one tiny example of each shape in Python.
def first_item(a): # O(1): one step, any size
return a[0]
def binary_search(a, target): # O(log n): halve the range each time
low, high = 0, len(a) - 1
while low <= high:
mid = (low + high) // 2
if a[mid] == target:
return mid
if a[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
def total(a): # O(n): one pass
result = 0
for x in a:
result += x
return result
def sort_then_scan(a): # O(n log n): sorting dominates
a = sorted(a)
return [a[i] for i in range(len(a))]
def count_pairs(a): # O(n^2): a loop inside a loop
count = 0
for x in a:
for y in a:
count += 1
return count
The binary search needs a sorted list. That is the price of halving.
The log here means log base 2. It answers one question: how many times can you cut 1,000 in half before you reach 1? About 10 times. The count barely moves when n grows. That is why O(log n) is so good.
Count steps, not seconds
Tara's first idea is a stopwatch. It fails for two reasons.
First, the same code gives different times. In one test, the same check on the same 2,000 IDs took between 0.073 and 0.103 seconds across seven runs. Second, small inputs lie. On 10 IDs, a slow method can beat a fast one.
So Sam shows her a better way. Pick one basic step that the code repeats. Count how many times it runs. Write the count as a formula in n.
Pause and predict
Before you run the counter: when n goes from 8 to 16, how many times bigger does the loop-inside-a-loop count get?
Answer: Four times bigger. It goes from 64 to 256. The single loop only doubles, and the halving count goes up by one.
Tara adds a counter next to three loops and doubles n each time.
def count_steps(n):
one_loop = 0
for _ in range(n):
one_loop += 1
nested = 0
for _ in range(n):
for _ in range(n):
nested += 1
halving = 0
x = n
while x > 1:
x //= 2
halving += 1
return one_loop, nested, halving
for n in (8, 16, 32, 64):
print(n, count_steps(n))
| n | One loop | Loop inside a loop | Halving |
|---|---|---|---|
| 8 | 8 | 64 | 3 |
| 16 | 16 | 256 | 4 |
| 32 | 32 | 1,024 | 5 |
| 64 | 64 | 4,096 | 6 |
Try it
Change the last line of the counter to for n in (100, 1000): and run it. Guess the nested count first.
For n = 100 you get 100, 10,000 and 6. For n = 1000 you get 1,000, 1,000,000 and 9. The nested count is n × n. Halving only moved from 6 to 9.
Look at what happens when n doubles. One loop doubles. A loop inside a loop becomes four times bigger. Halving goes up by just one. The shape of the growth is what Big-O describes.
These rules turn a count into Big-O:
- Drop constants. 2n becomes n.
- Keep only the biggest term. n² + 5n + 20 becomes n².
- Loops in a row add. n + n is O(n).
- Loops inside loops multiply. n × n is O(n²).
- Two different inputs need two letters. A loop over n items with an inner loop over m items is O(n × m).
Big-O hides constants, so it is not the whole truth. Two O(n) methods can still differ a lot in speed. Use Big-O to choose the method. Then measure if the gap matters.
Time is not the only cost
Memory is a cost too. Space complexity is how the extra memory grows when n grows. "Extra" means memory the code creates beyond the input itself.
Tara checks three ways to find a repeated order ID. She measures their peak extra memory in Python.
import tracemalloc
def peak_extra_bytes(func, *args):
tracemalloc.start()
func(*args)
_, peak = tracemalloc.get_traced_memory()
tracemalloc.stop()
return peak
ids = [f"VA{i}" for i in range(2000)]
print(peak_extra_bytes(has_duplicate_pairs, ids))
print(peak_extra_bytes(has_duplicate_set, ids))
The functions has_duplicate_pairs and has_duplicate_set are the two duplicate checks from the first article.
- Pair check: about 284 bytes at 1,000 IDs and at 2,000 IDs. It stays the same, so it is O(1).
- Sort first: it makes a new list. This costs about 12 bytes per ID in her test. It grows with n, so it is O(n).
- Set: it grows with n too, so it is O(n). At 200,000 IDs it used about 12.6 million bytes.
The set method buys speed with memory. A server can afford that trade. A phone with little memory may not. You decide based on where the code runs.
These numbers were measured on one machine. They will differ on yours. The shape will not.
Spot the shape in your own code
Use three clues on any code you read or write.
- Name n. Is it one list? Two lists? A number? Say it before you count.
- Watch how each loop moves. Does it run n times, fewer times, or does it halve? Loops in a row add. Nested loops multiply.
- Check every call inside a loop. A short line can hide a loop.
Here is a hidden loop. Tara builds a list of 80,000 numbers two ways. One way adds each number at the front with insert(0, x). The other adds at the end with append(x).
import time
def build_front(n):
a = []
for i in range(n):
a.insert(0, i) # moves every item each time
def build_end(n):
a = []
for i in range(n):
a.append(i) # no moving
for f in (build_front, build_end):
start = time.perf_counter()
f(80_000)
print(f.__name__, round(time.perf_counter() - start, 4))
- Insert at the front: 0.695 seconds.
- Append at the end: 0.002 seconds.
Both are one short line. But each front insert moves every item one place. That is O(n) each time, and O(n²) in total. When n doubled in her test, the insert time went up about four times.
Other hidden loops in Python are x in my_list, pop(0), slices, .count() and .index().
Finally, say the cost out loud. Use this template:
"This takes about O([time shape]) time, because [reason]. It uses O([space shape]) extra space, because [reason]."
Tara says it for the set method: "This takes about O(n) time. I go through the IDs once, and each set check is one look on average. It uses O(n) extra space, because the set can hold every ID."
Two sentences. No guessing. The reason after each "because" shows you know where the cost comes from.
Takeaway: Name n. Count one basic step. Drop constants and keep the biggest term. Always say time and space.