Example 1 — Count comparisons, then classify
Show the steps and the answer
Method A: the running maximum starts as the first number and is compared with each of the other n − 1 numbers: 9 comparisons for n = 10, 19 for n = 20.
One loop over the list means one comparison per item, give or take one.
Method B: the first number is compared with the 9 after it, the next with 8, and so on: for n = 10, and for n = 20.
This is a loop inside a loop: each item starts its own pass through the items after it, giving comparisons.
Compare growth: doubling n took A from 9 to 19 (about ×2) and B from 45 to 190 (about ×4).
Work that doubles with the input is the signature of linear growth; work that quadruples is the signature of quadratic growth.
Drop constants and smaller terms: is , and is .
Big-O keeps only the term that dominates for large n and ignores its coefficient.
Answer: A: 9 and 19 comparisons, . B: 45 and 190 comparisons, .
Takeaway: One pass over the data is linear; a loop inside a loop over the same data is quadratic. Doubling n shows which one you have.