How it works
Efficiency describes how work grows as input size grows, not just whether code finishes for one small example.
Compare single loops, nested loops, sequential search, and binary search by how many steps they may take.
Common error
Binary search only applies when the data is sorted and the algorithm can repeatedly eliminate half the search range.
Worked example
Compare growth in work rather than the speed of one small run.
Data / pseudocode
Algorithm A: checks each of n items once
Algorithm B: checks each pair in two full n loops
When n = 100: A = 100 checks; B = 10000 checksA grows linearly with n, while the two full nested loops in B grow quadratically. Doubling n doubles A work and multiplies B work by four under this model. Actual runtime also depends on implementation and hardware; the growth comparison concerns counted operations.
Exercises
3.4.1
For two full nested loops each running n times, how many body executions occur at n = 20 and n = 40?
Show solution
At n = 20 there are 400 executions; at n = 40 there are 1600, which is four times as many.
3.4.2
Why can binary search eliminate half a sorted search range after comparing the midpoint, and why does the same argument fail on an unsorted list?
Show solution
Sorted order tells which side can contain the target. Without that order, a smaller midpoint value gives no reliable information about where other values lie.