Exercise 1: Three Sequential Loops — Possible Solution ==================================================================== GIVEN ------------------------------ Loop 1: over n items Loop 2: (sequential, not nested) over a fixed 50-item list Loop 3: (sequential, not nested) over the same n items again STEP 1: THE OPERATION COUNT FOR EACH LOOP ------------------------------ Loop 1: n operations Loop 2: 50 operations (a fixed constant, unrelated to n) Loop 3: n operations STEP 2: APPLYING THE SUM RULE ------------------------------ Per this chapter's own sum rule, sequential (non-nested) blocks add their operation counts: Total = n + 50 + n = 2n + 50 STEP 3: SIMPLIFYING WITH THE DOMINANT-TERM RULE ------------------------------ Per Chapter 2's own dominant-term rule, the fastest-growing term is 2n; the constant 50 and the coefficient 2 are both dropped: Overall complexity: O(n) WHY THE 50-ITEM LOOP DOESN'T CHANGE THE ANSWER ------------------------------ The 50-item loop contributes a fixed, constant amount of work that never grows no matter how large n becomes - it's exactly the kind of term the dominant-term rule is built to discard. As n grows very large, the 50 extra operations become an ever-shrinking fraction of the total work, eventually negligible, which is precisely why Big-O notation ignores it entirely. WHY THIS WORKS AS AN ANSWER ------------------------------ Each loop's own operation count is stated individually, the sum rule is applied explicitly to combine them (rather than the product rule, since these loops are sequential, not nested), and the final simplification is justified using Chapter 2's own dominant-term reasoning rather than just stating the answer.