Unit 4 · Algorithms & Simulation · Lesson 4.6

Measuring Efficiency Without Big-O

No formulas, no notation — just counting. One loop, two loops, a loop inside a loop. Count the innermost line on small inputs, spot the pattern, and you can compare any two algorithms the exam throws at you.

Big Idea 3 — Algorithms & ProgrammingCED 3.17 · Lab 4.6

Before this lesson

No reading — this page is the reading. Runestone doesn’t cover Unit 4 (search, efficiency, limits, simulation), so everything you need is right here.

Where We Are

People→ Bits→ Programs→ Internet→ Security→ Big Data→ Impact

Programs, Algorithms region — Week 2. Last week you counted the steps of two specific algorithms. This week the counting works on any code, and then runs into the edge of what computers can do at all.

The Hook

Same output. Wildly different step counts. Two procedures both answer “does this list have a duplicate?” On 10 records, one takes 10 steps and the other takes 100. On a million records, one takes a million steps. The other takes a trillion.

Which would you rather run? You don’t need a formula to answer that — you need to be able to count.

The Idea

Count how many times the innermost line runs. Three shapes cover almost everything on the exam:

Shape	Innermost line runs	n = 3	n = 4	n = 5	Described as
One loop over the list	n	3	4	5	linear growth
Two loops, one after the other	n + n	6	8	10	still linear
A loop inside a loop	n × n	9	16	25	quadratic growth

Python — a loop inside a loop

count = 0
for a in nums:
    for b in nums:
        count = count + 1  # innermost
print(count)

AP Pseudocode

count ← 0
FOR EACH a IN nums
{ FOR EACH b IN nums
  { count ← count + 1 } }
DISPLAY(count)

For every one of the n values of a, the inner loop runs all n values of b. n groups of n: n × n. With 5 items, 25. With 10 items, 100.

The testable skill is comparison, not notation. The exam never asks for Big-O. It asks “does this take about n steps or about n² steps?” and “what happens when the input doubles?” Linear: double the input, double the work. Quadratic: double the input, four times the work.

Try It — Watch the Work Pile Up

Each square is one run of the innermost line. Pick a shape, then grow n.

shape:

n = 5

Lab 4.6 — Efficiency Day

Three procedures, three growth rates. Predict before you code — your predictions are graded for existing, not for being right. Then instrument each one with a counter and fill in the growth table for n = 3, 5, and 10.

Vocabulary

algorithmic efficiency Programs: An estimate of how much work an algorithm needs as its input grows — found by counting steps, not by timing a stopwatch.
linear growth Programs: Work that grows in proportion to n. Double the input, double the work. (One loop.)
quadratic growth Programs: Work that grows like n × n. Double the input, four times the work. (A loop inside a loop.)

Check

Five questions. For each one, find the innermost line first, then count.

0 of 5 answered

Impact Check

The features you never got

Suppose a social network wanted to suggest friends by comparing every user to every other user. With 3 billion users, that’s a loop inside a loop: about 9 × 10¹⁸ comparisons. At a billion comparisons a second, one pass takes roughly 285 years.

So nobody builds it that way. Engineers throw out quadratic designs at that scale and find cleverer ones — or drop the feature. Efficiency quietly decides which features exist at all.

Connections

Came from 4.1 + 4.5 — 4.1’s Algorithm B was a loop inside a loop. Now you can say why it lost: quadratic vs linear.

Next in 4.7 — n² is slow but reasonable. Some growth rates are not.

Uses 3.8 — nested traversal; the trace table already shows a step count.

Returns on the exam — “how many times does this line run?” with nested loops, and “which algorithm is more efficient?”