Analyzing Control Structures

Analyzing Control Structures

You already know that some algorithms are "fast" and some are "slow." But where does a running-time formula like O(n2) actually come from? It is not magic and it is not guessing. It comes from reading the code and adding up work, one control structure at a time. Analyzing control structures is the mechanical skill of walking through the sequences, conditionals, and loops of a program and turning them into a cost function. Once you can do this by hand, complexity classes stop being labels you memorize and become numbers you can derive.

The core idea is simple: every basic operation costs a constant amount of time, and the total cost is just the sum of costs of the pieces. The whole game is figuring out how many times each piece runs.

Precise definition

We count primitive operations (arithmetic, comparisons, assignments, array indexing, returns) and assume each takes constant time. Let T(n) be the number of such operations as a function of input size n. We then bound T(n) asymptotically. Three composition rules cover every structured program:

• Sequence (statement A then B): costs add. T = TA + TB. When bounding with big-O, the larger term dominates: O(f) + O(g) = O(max(f, g)).
• Conditional (if C then A else B): cost is the test plus whichever branch runs. For a worst-case upper bound we take the more expensive branch: TC + max(TA, TB).
• Loop: cost is the sum, over every iteration, of the body's cost for that iteration. If the body is constant and the loop runs k times, cost is k. If the body's cost varies per iteration, you must sum the series, not just multiply.

Nested loops compose by nesting the sums: the inner loop is the "body" of the outer loop.

Worked example — count the operations

Consider this fragment that sums, for each i, all elements up to i (a deliberately wasteful design):

• 1 total = 0
• 2 for i = 0 to n-1:
• 3   for j = 0 to i:
• 4     total = total + A[j]
• 5 return total

Line 1 runs once. Line 5 runs once. The interesting cost is line 4. For a fixed i, the inner loop runs i + 1 times. So the total number of executions of line 4 is:

Σi=0n-1 (i + 1) = 1 + 2 + 3 + … + n = n(n+1)/2

Plug in n = 4: the inner body runs 1 + 2 + 3 + 4 = 10 times, and 4·5/2 = 10. It checks out. That formula equals n2/2 + n/2. As n grows the n2/2 term swamps everything, so we drop the lower-order term and the constant factor: the algorithm is Θ(n²). Notice the trap: the outer loop runs n times and the inner loop runs "up to n" times, but multiplying n × n = n2 gives the right class only by luck here — the exact count is n(n+1)/2, which you get by summing the series, not multiplying the maxima.

Best, worst, and average case

Control-structure analysis often gives different counts depending on the input, and conditionals plus early exits are where this shows up. Take linear search for a key in an array of n items: a loop with an if found: return inside.

• Best case: the key is at index 0. The loop body runs once → Θ(1).
• Worst case: the key is absent or last. The body runs n times → Θ(n).
• Average case: assuming the key is equally likely at any position, the expected number of comparisons is (1 + 2 + … + n)/n = (n+1)/2 → still Θ(n).

Best/worst/average are answers to three different questions and should be stated separately; collapsing them is a common source of wrong conclusions. Big-O bounds the growth; which case you are bounding is a separate choice you must declare.

Pitfalls interviewers probe

• Multiplying maxima instead of summing. For nested loops where the inner bound depends on the outer index, n × n gives the correct big-O class but the wrong exact count. Interviewers ask "how many times exactly?" to see if you can sum Σi. Know that 1+2+…+n = n(n+1)/2 and 1+2+4+…+2k = 2k+1-1.
• Assuming loop count equals the variable's range. A loop while i < n: i = i*2 runs Θ(log n) times, not n times, because i multiplies rather than increments. Always ask how the loop variable changes.
• Hidden costs inside "one line." A line like result += list[1:] or if x in myList can hide an O(n) copy or scan. A single statement is only O(1) if every operation in it truly is.
• Recursion is a control structure too. A recursive call's cost is captured by a recurrence like T(n) = 2T(n/2) + O(n); you solve it (recursion tree / Master Theorem) rather than reading loop bounds.

Why it matters in practice

This skill is how you move between neighbouring complexity classes deliberately rather than by accident. Seeing that a nested loop produces Θ(n2) tells you it will not survive n = 106 (that is 1012 operations — minutes to hours), which is your cue to look for an O(n log n) sort-based approach or an O(n) hashing pass. Conversely, when you turn a doubling loop into Θ(log n), you know the input can grow astronomically at almost no cost.

The trade-off is that constant factors and lower-order terms — exactly what this counting exposes — do matter at real-world scales. An O(n) algorithm with a huge constant can lose to an O(n log n) one for the inputs you actually have. Counting operations by control structure is what lets you make that call with numbers instead of hand-waving.

Key takeaways

• Sequence adds, conditional takes the (worst-case) branch, loop sums the body over all iterations — three rules compose to analyze any structured program.
• For nested loops with a dependent inner bound, sum the series (Σi = n(n+1)/2); multiplying maxima gives the right class but the wrong exact count.
• Watch how the loop variable changes: incrementing gives Θ(n), doubling gives Θ(log n), and "one line" may hide an O(n) cost.
• Always state which case (best / worst / average) you are bounding — they answer different questions.