DSA · Analysis

Count the operations, not the seconds

Q: Two loops one after the other — do you add or multiply?

Add. Each loop runs n times, so the total is n + n = 2n , which is O(n). You multiply only when one loop sits inside the other, which gives n × n . Indentation is the only difference between the two cases, and mixing them up is the single most common counting mistake.

Complexity is arithmetic you can do on paper. You will count a single loop and a nested loop over the same n, watch the operation table fill box by box, and learn to read a constraint like n ≤ 100,000 as a rough budget of about 100 million operations.

Fill the operation table, one pass at a time →

n = 100,000one input size · two loop shapes

→

single loop100,000 operations · about 0.001 s

→

nested loop10,000,000,000 operations · about 100 s

01 The idea

A formula in n, not a stopwatch reading

You cannot judge an algorithm by timing it. The same code finishes in half a second on a new laptop and two seconds on an old lab machine, and neither number tells you what happens when the input gets ten times bigger. So you count instead. Pick one basic operation — a comparison, an addition, an array read — and work out how many times it runs, written as a formula in the input size n.

That formula is where the answer lives. A single loop over n items runs its body n times. Put a second loop inside it and the body runs n × n times. At n = 5 that is 5 against 25, which looks harmless. At n = 100,000 it is 100,000 against 10,000,000,000, and on a machine that manages roughly 100 million simple operations a second the first finishes instantly while the second takes about a hundred seconds. Same body, same language, same machine. Only the shape of the loops changed.

Then you throw most of the formula away. 5n² + 100n + 3000 is called O(n²). At n = 1,000 the first term is 5,000,000 out of a total 5,103,000, so the other two contribute about 2 per cent, and their share keeps shrinking as n grows. The coefficient 5 goes too, because it depends on your language and your compiler while the exponent does not.

Count the basic operations as a formula in n, keep only the fastest-growing term, and drop its coefficient. What survives is the complexity.

Basic operationOne step whose cost does not change with n: a comparison, an addition, an array read, an assignment. You count these rather than seconds, because seconds change with the machine and the count does not.

Growth rateWhat happens to the operation count when n doubles. The count doubling is linear, quadrupling is quadratic, and going up by a single step is logarithmic.

Big-OAn upper bound on the growth rate with constants ignored. O(n²) means "past some input size this never grows faster than a fixed multiple of n²". Interviewers want the tightest bound you can defend.

02 Worked example

Counting a single loop and a nested loop at n = 5

One input size, two loop shapes, and the identical one-line body in both: count = count + 1. Counting operations therefore means counting how many times that one line runs. Every box below is one execution of it, numbered in the order it happens. The rose row is a single pass of the outer loop, drawn out in full; the emerald rows are the passes that follow.

Single loop — the body runs once per pass

i = 01+1 · total 1

i = 12+1 · total 2

i = 23+1 · total 3

i = 34+1 · total 4

i = 45+1 · total 5 = n

Nested loop — the body runs n times per pass

i = 012345+5 · total 5

i = 1678910+5 · total 10

i = 21112131415+5 · total 15

i = 31617181920+5 · total 20

i = 42122232425+5 · total 25 = 5 × 5

Five boxes against twenty-five. Now put both counts in a table and extend them, because a single value of n tells you nothing — the whole subject is about what happens as n moves.

Loop shape	Operations at n = 5	At n = 10	At n = 100	Formula	Big-O
Single loop	5	10	100	n	`O(n)`
Nested loop	25	100	10,000	n × n	`O(n²)`

Read the table down each column rather than across each row. Multiply n by 10 and the single loop multiplies its work by 10; the nested loop multiplies its work by 100. That relationship is the complexity, and it is fixed by the shape of the code before you know anything about the machine it will run on.

03 Reading a loop

Four shapes, two rules, and the memory bill

Almost every complexity you will be asked to state in a first round comes out of four loop shapes and two rules. Nesting multiplies. Sequencing adds. The rest is arithmetic on the formula you already have.

Single loop — O(n)

count = 0for i in 0 .. n-1:            # runs n times    count = count + 1         # one basic operation# total = n operations   ->   O(n)

Nested loop — O(n²)

count = 0for i in 0 .. n-1:            # outer runs n times    for j in 0 .. n-1:        # inner runs n times, every pass        count = count + 1     # one basic operation# total = n x n operations   ->   O(n^2)

Why nesting multiplies. The outer loop runs n times. Each one of those passes runs the whole inner loop, which is n more operations. n copies of n is n × n. The nested trace above is that sentence drawn out: five rows, five boxes in each row, twenty-five boxes.

Why the size of the body does not change the class. Replace count = count + 1 with ten lines that each cost O(1) and the nested version costs 10n². Drop the 10 and it is still O(n²). Constants inside the body change the wall-clock time. They cannot change how the time grows.

Sequential loops — O(n)

for i in 0 .. n-1:  a = a + 1    # nfor j in 0 .. n-1:  b = b + 1    # n# total = n + n = 2n   ->   O(n)

Halving loop — O(log n)

k = nwhile k > 1:    k = k // 2              # integer halve; n=5: k goes 5, 2, 1# total = about log2(n)   ->   O(log n)

Why sequential loops add. Two loops one after the other each run n times, so the body runs 2n times altogether, and 2n is O(n). Marks are lost here by multiplying instead: n × n is what you get when the second loop sits inside the first, and the indentation is the only thing that tells the two apart.

Where log n comes from. Halving is the whole story. Ask how many times you can halve n before you reach 1 — halving with integer division, that count is ⌊log₂ n⌋, which is why everyone just says log₂ n. At n = 5 it is 2, because k goes 5, 2, 1. It grows painfully slowly: 1,000 needs about 10 halvings and 1,000,000 needs about 20, so a thousand times more data costs ten more steps rather than a thousand times more work. Any loop that throws away a constant fraction of what is left on every pass has this shape — binary search, walking down a balanced tree, repeated doubling.

Here is what the four shapes actually cost. The log₂ n and n log₂ n columns are rounded to the nearest whole number — 100 × log₂ 100 is really 664.4 — while the O(1), O(n) and O(n²) columns are exact.

n	O(1)	O(log n)	O(n)	O(n log n)	O(n²)
10	1	3	10	33	100
100	1	7	100	664	10,000
1,000	1	10	1,000	9,966	1,000,000
100,000	1	17	100,000	1,660,964	10,000,000,000
1,000,000	1	20	1,000,000	19,931,569	1,000,000,000,000

Read the bottom row from left to right. At n = 1,000,000 the O(n log n) column is 19,931,569 operations, which is about a fifth of a second. The O(n²) column is 1,000,000,000,000, which is about three hours on the same machine. That is what people mean when they say a quadratic solution does not scale. It is not slower. It is unusable.

Space complexity: auxiliary or total

The same counting, applied to memory instead of time. Total space is the input plus everything the algorithm allocates. Auxiliary space is only what the algorithm adds on top of the input. They differ by exactly the size of the input, which sounds like hair-splitting until an interviewer asks for the space complexity of an in-place reversal and you have to pick one.

What the code does	Auxiliary space	Total space	Why
Reverse an array in place	`O(1)`	`O(n)`	Two indices and one temporary variable, whatever n is. The array itself was already there.
Merge sort with a buffer	`O(n)`	`O(n)`	The merge buffer holds n elements, and the recursion adds O(log n) frames on top of it.
Sum n items recursively	`O(n)`	`O(n)`	It allocates nothing, but n call frames are alive at the deepest point and each one is real memory.

Say which one you mean. In interviews "space complexity" almost always means auxiliary, and the recursion stack counts towards it — a recursive sum over n items uses O(n) auxiliary space even though it never allocates a single array.

05 Cheat sheet

The two tables to check before an interview

The first table tells you what a complexity class behaves like. The second tells you which class the problem is asking for, read straight off the constraint line.

Class	Name	What doubling n does	Where it comes from
`O(1)`	Constant	Nothing changes	Array index, arithmetic, hash lookup, pushing onto a stack
`O(log n)`	Logarithmic	Adds one step	Halving loop, binary search, height of a balanced tree
`O(n)`	Linear	Doubles the work	One pass over the input
`O(n log n)`	Linearithmic	A little more than doubles	Sorting, divide and conquer, a log-time operation per element
`O(n²)`	Quadratic	Multiplies by 4	A nested loop over every pair
`O(2ⁿ)`	Exponential	Squares the count	Every subset of n items. At n = 100,000 the count has 30,103 digits.
`O(n!)`	Factorial	No useful rule	Every permutation. 20! is already 2.4 × 10¹⁸.

Constraint says	Complexity the constraint points at	Operations at that n	What you are being asked for
n ≤ 11	`O(n!)`	39,916,800	Try every permutation
n ≤ 25	`O(2ⁿ)`	33,554,432	Every subset, bitmask over states
n ≤ 500	`O(n³)`	125,000,000	Triple loop, all-pairs shortest paths
n ≤ 5,000	`O(n²)`	25,000,000	A table over every pair of indices
n ≤ 100,000	`O(n log n)`	1,660,964	Sort it, or do one log-time step per element
n ≤ 10,000,000	`O(n)`	10,000,000	A single pass, no sorting
n ≤ 10¹⁸	`O(log n)`	about 60	Binary search on the answer, or a closed-form formula

Every count in that third column is the complexity multiplied out at the largest allowed n, so read it as an order of magnitude and not as a promise. The O(n³) row lands at 1.25 × 10⁸, already past the rule of thumb below, and it still passes in practice because one pass of a triple loop is usually two array reads and an addition. That is exactly why 10⁸ is a rule of thumb: a count two or three times over it can survive, and a count a hundred times over it never does.

The 100-million rule of thumbAssume very roughly 10⁸ simple operations per second — an order of magnitude, not a law, because the real figure moves with the language and with how heavy one operation is. Multiply your complexity out at the largest allowed n: comfortably under 10⁸ is safe, far over it needs a different algorithm, and anything within a few times of 10⁸ has to be measured.

Auxiliary vs total spaceAuxiliary is what your algorithm adds; total includes the input. In-place reversal is O(1) auxiliary and O(n) total, and recursion frames count as auxiliary.

Keep the leader, drop the rest5n² + 100n + 3000 is O(n²). The coefficient depends on your language and compiler. The exponent does not, which is why only the exponent survives.

06 Where & why

Big-O is a filter, not a verdict

Complexity tells you which algorithms are even allowed for the input size you were handed. It deliberately hides the constant factors, so it cannot tell you which of the surviving candidates will actually be fastest on your data. Knowing which of those two questions you are answering is most of the skill.

Trust the Big-O when…

The constraint is written downn ≤ 100,000 is an instruction, not decoration. Work out the budget first, pick the class that fits it, and only then start writing code.

You are comparing different classesO(n log n) against O(n²) at n = 100,000 is 1,660,964 against 10,000,000,000. No amount of tuning closes a gap of six thousand times.

n can grow without warningA log table that is fine at 10,000 rows today will be 10,000,000 rows next year. The class decides whether that is a non-event or an outage.

You need to predict, not measureBig-O tells you what happens when the data becomes ten times larger, before that data exists and before there is anything to benchmark.

Look past the Big-O when…

Situation	Better guide	Why
n is small and genuinely bounded	The simpler algorithm, then a measurement	At n = 100 a quadratic loop is 10,000 operations, which is microseconds. Correctness and readability are worth more than the exponent.
Two candidates sit in the same class	Constant factors and cache behaviour	Timsort and a textbook merge sort are both O(n log n), but Timsort wins on partly sorted data because of exactly what Big-O throws away.
Average and worst case diverge	The worst case, stated out loud	Hash lookup is O(1) average and O(n) worst; quicksort is O(n log n) average and O(n²) worst on adversarial input.
Memory is the binding limit	Space complexity	An O(n log n) sort that allocates an O(n) buffer can blow a 256 MB limit while a slower in-place algorithm survives it.

In an interview, state the complexity before you write the code, and say three things: which case you mean, whether the space is auxiliary or total, and what n the constraint allows. Most of the marks in an analysis question come from being precise about those, not from finding a smaller exponent.

07 Interview questions

What interviewers actually ask

Twelve questions in the order an interview escalates: what it is, how you count it, where each class comes from, and then the constraint-reading question that decides which solution you are supposed to write.

What is time complexity?

It is a count of basic operations written as a function of the input size n, not a measurement in seconds. Seconds depend on the machine, the language and the compiler; the operation count depends only on the code. You use it to predict how the running time changes when the input grows, which is the one thing a stopwatch on your own laptop cannot tell you.

Why do you drop constants and lower-order terms?

Because they stop mattering as n grows, and they are machine-dependent anyway. In 5n² + 100n + 3000 at n = 1,000, the first term is 5,000,000 out of 5,103,000 — the rest is about 2 per cent and shrinking. The coefficient 5 changes if you switch language or compiler; the exponent 2 does not, so only the exponent is worth stating.

What does Big-O actually mean?

It is an upper bound on growth: f(n) is O(g(n)) if past some input size, f never grows faster than a fixed multiple of g. In practice that reduces to "keep the fastest-growing term, drop its coefficient". Because it is only an upper bound, O(n) code is technically also O(n²) — interviewers expect the tightest bound you can defend, so say O(n).

Two loops one after the other — do you add or multiply?

Add. Each loop runs n times, so the total is n + n = 2n, which is O(n). You multiply only when one loop sits inside the other, which gives n × n. Indentation is the only difference between the two cases, and mixing them up is the single most common counting mistake.

The inner loop starts at i instead of 0. What is the complexity now?

Still O(n²). With j running from i up to n−1, the inner loop does n iterations on the first outer pass, then n−1, then n−2, down to 1 — and that sum is n(n+1)/2, which is (n² + n)/2. Drop the ½ and the +n and n² is what is left. At n = 5 it is 15 operations instead of 25: a bit over half the work, and exactly the same growth class. (Start j at i+1 instead and the sum is n(n−1)/2, which is 10 at n = 5 — still O(n²).)

Where does log n come from?

From cutting the problem by a constant factor on every pass. A loop that does k = k/2 until k reaches 1 runs about log₂ n times, because that is how many halvings n survives. It grows extremely slowly: 1,000 takes about 10 steps and 1,000,000 takes about 20, so a thousand times more data costs ten more steps. Binary search and the height of a balanced tree are the same shape.

Does Big-O mean the worst case?

Not by itself. Big-O is notation for an upper bound; best, average and worst are separate cases you can each describe with it. When people say "the complexity is O(n log n)" they usually mean the worst case, because that is what you have to plan for. Be explicit: linear search is O(1) in the best case and O(n) in the worst, and saying only one of those is what gets you caught.

What is the difference between auxiliary and total space?

Total space counts the input plus everything the algorithm allocates. Auxiliary space counts only the extra. Reversing an array in place is O(1) auxiliary and O(n) total. Interviews almost always mean auxiliary, and the recursion stack counts towards it — a recursive sum over n items is O(n) auxiliary even though it never allocates an array.

The constraint says n ≤ 100,000. What does that tell you?

That you need O(n log n) or better. Assume about 10⁸ simple operations per second: at n = 100,000, O(n log n) is roughly 1.7 million and O(n) is 100,000, both trivially inside the budget. O(n²) is 10,000,000,000, which is a hundred times over. So the constraint is really an instruction to sort, use a heap, or do one log-time operation per element.

And n ≤ 20?

That an exponential solution is intended. 2²⁰ is about 1.05 million, which is nothing, while 20! is 2.4 × 10¹⁸, which is impossible. So subsets are on the table and permutations are not — read it as a hint towards bitmask enumeration or brute force over states, not as the problem being easy.

Two sorts are both O(n log n) but one runs twice as fast. How?

Hard

For for i in 1..n: k = i; while k > 1: k = k // 2, state the Big-O of the total operation count and justify both an upper and a lower bound.

Follow-up

The inner loop’s length changes with i, so you cannot multiply the two loop bounds together and call that an answer — the honest total is a sum, and it has to be squeezed from above and from below. The lower bound is the half of the question people skip, and it is where the marks are.

Show the hint

For a given i the inner loop runs about log₂ i times, so the total is the sum of log₂ i for i = 1 to n. Bound that sum from above by replacing every term with the largest term. Bound it from below by keeping only the largest half of the terms and throwing the rest away.