Day 83 — Loops → sums → bounds

Day 83 — Loops to sums to bounds; amortized idea

Stage VIII · concept day
Goal: Translate nested loops to sums; bound sums by closed forms or integral ideas; set up best/worst/average; introduce amortized analysis idea (aggregate method, dynamic array doubling).

Why this matters

Runtime analysis is usually “count elementary steps → sum → asymptotics.” Master theorem (Day 84) handles recurrences; today handles straight-line nested iteration and the first amortized stories you meet for resizable arrays.

Note

No labs. Static pseudocode only; analyze on paper.

---

Theory

From loops to sums

Model. Each “elementary operation” costs \(1\). Loops contribute a sum over the iteration domain.

Single loop.

for i = 1..n:
    work O(1)

Cost \(T(n)=\sum_{i=1}^n \Theta(1)=\Theta(n)\).

Independent nested loops.

for i = 1..n:
  for j = 1..n:
      work O(1)

\(T(n)=\sum_{i=1}^n\sum_{j=1}^n 1=n^2=\Theta(n^2)\).

Triangular nested loops.

for i = 1..n:
  for j = 1..i:
      work O(1)

\(T(n)=\sum_{i=1}^n i = n(n+1)/2=\Theta(n^2)\).

Dependent bounds.

for i = 1..n:
  for j = i..n:
      work O(1)

\(\sum_{i=1}^n (n-i+1)=\sum_{k=1}^n k=\Theta(n^2)\).

Standard sum catalogue

Sum	Closed form / bound
\(\sum_{i=1}^n 1\)	\(n\)
\(\sum_{i=1}^n i\)	\(n(n+1)/2=\Theta(n^2)\)
\(\sum_{i=1}^n i^2\)	\(n(n+1)(2n+1)/6=\Theta(n^3)\)
\(\sum_{i=1}^n i^k\) (\(k\) fixed)	\(\Theta(n^{k+1})\)
\(\sum_{i=1}^n \log i\)	\(\Theta(n\log n)\) (Stirling / integral)
\(\sum_{i=0}^h 2^i\)	\(2^{h+1}-1=\Theta(2^h)\)
\(\sum_{i=1}^n 1/i\)	\(H_n=\Theta(\log n)\)

Bounding sums by integrals (idea)

For nondecreasing \(f\), \[ \int_0^n f(x)\,dx \le \sum_{i=1}^n f(i) \le f(n)+\int_0^{n-1} f(x)\,dx \] (pictorial staircase bounds). For nonincreasing, inequalities reverse appropriately.

Example. \(\int_1^n (1/x)\,dx=\ln n\) sandwiches \(H_n\): \(\ln(n+1)\le H_n\le 1+\ln n\), so \(H_n=\Theta(\log n)\).

Best / worst / average case (setup)

For input size \(n\), cost may depend on the particular input \(x\) with \(|x|=n\).

• Worst case: \(T_{\mathrm{wc}}(n)=\max_{|x|=n} T(x)\).
  
• Best case: \(T_{\mathrm{bc}}(n)=\min_{|x|=n} T(x)\).
  
• Average case: \(T_{\mathrm{avg}}(n)=\sum_{|x|=n} T(x)P(x)\) under a stated distribution on inputs.

Always label which case. Average case requires a probability model (Day 85+).

Example. Linear search for a key in an array of \(n\) distinct keys: best \(\Theta(1)\), worst \(\Theta(n)\), average \(\Theta(n)\) under uniform position of the key (including failure variants carefully).

Amortized analysis (idea)

Problem. Some operations are occasionally expensive (array resize) but rare. Amortized cost of an operation in a sequence is a bound on average cost over the sequence, not a probability.

Aggregate method. If any sequence of \(n\) operations costs at most \(T(n)\) total, the amortized cost per operation is \(T(n)/n\).

Dynamic array doubling.

• Array capacity \(c\), size \(m\).
  
• Append: if \(m<c\), cost \(1\); if \(m=c\), allocate \(2c\), copy \(m\) elements, then insert — cost \(\Theta(m)\), then \(c\leftarrow 2c\).
  
• From empty to \(n\) appends: resizes at sizes \(1,2,4,\ldots,2^{k}\) with \(2^k<n\le 2^{k+1}\). Copy costs \(1+2+4+\cdots+2^k < 2n\).
  
• Total cost of \(n\) appends: \(O(n)\) (all cheap inserts) \(+O(n)\) (all copies) \(=O(n)\).
  
• Amortized \(O(1)\) per append.

Accounting / potential methods (awareness). Assign banked credits or a potential function \(\Phi\) so amortized cost \(=\text{actual}+\Delta\Phi\) is bounded; aggregate doubling is enough for this volume.

Not the same as average case. Amortized is adversarial sequences with total bound; average case is random inputs.

Nested loops with geometric iteration

for i = 1,2,4,...,2^k < n:
    work O(i)   # or O(n), depending

Number of iterations \(O(\log n)\). If work per iteration is \(O(n)\), total \(O(n\log n)\). If work is \(O(i)\), total \(O(n)\).

Sequential vs nested

Sequential blocks: add costs. Nested: multiply iteration counts (when inner independent of outer cost structure) — more precisely, sum the inner costs.

---

Worked examples

Example 1 — Triangular.
\(\sum_{i=1}^n\sum_{j=1}^i 1=\sum_i i=\Theta(n^2)\).

Example 2 — Three nested.
Triple independent loops \(n\times n\times n\): \(\Theta(n^3)\).

Example 3 — Log factor.

for i=1..n:
  j=n
  while j>=1:
    j = j//2

Inner runs \(\Theta(\log n)\) times; total \(\Theta(n\log n)\).

Example 4 — Harmonic.

for i=1..n:
  for j=1..n step i:  # j = i,2i,3i,...
      O(1)

Inner runs \(\lfloor n/i\rfloor\) times; total \(\sum_{i=1}^n n/i = n H_n=\Theta(n\log n)\).

Example 5 — Best/worst.
Insertion into sorted array at beginning vs end may differ if shifting costs; specify model.

Example 6 — Doubling aggregate.
\(n=10\) appends: copies at capacities \(1,2,4,8\) costing \(1+2+4+8=15\) plus \(10\) writes = \(25=O(n)\).

Example 7 — Sum of squares.
\(\sum_{i=1}^n i^2=\Theta(n^3)\) so nested

for i=1..n:
  for j=1..i:
    for k=1..i:
        O(1)

is \(\sum_i i^2=\Theta(n^3)\).

Example 8 — Geometric series.
Cost \(1+2+4+\cdots+2^{h}=\Theta(2^h)\). If \(2^h=\Theta(n)\), total \(\Theta(n)\).

Example 9 — Average linear search.
Successful search, key uniform in \(n\) positions: expected comparisons \((n+1)/2=\Theta(n)\).

Example 10 — Misleading “each op \(O(n)\)”.
\(n\) appends each “\(O(n)\) worst” would suggest \(O(n^2)\), but amortized \(O(1)\) gives \(O(n)\) total — the point of amortization.

---

Exercises

A. Loop translations

1. Cost of double loop \(i=1..n\), \(j=1..n\).
   
2. Cost of \(i=1..n\), \(j=1..i\).
   
3. Cost of \(i=1..n\), \(j=i..n\).
   
4. Cost of \(i=1..n\), \(j=1..n\), \(k=1..n\).
   
5. Cost of \(i=1..n\), inner while \(j\leftarrow n, n/2, n/4,\ldots\)
   
6. Analyze Example 4 style: for \(i=1..n\) for \(j=i; j\le n; j+=i\).

B. Sums and bounds

7. Prove \(\sum_{i=1}^n i=\Theta(n^2)\) with sandwich \(n^2/2\le\sum i\le n^2\).
   
8. Show \(H_n=\Theta(\log n)\) using integral idea.
   
9. Bound \(\sum_{i=1}^n i^3\) as \(\Theta(n^4)\) (formula or integral).
   
10. Show \(\sum_{i=1}^n \log i=\Theta(n\log n)\).
    
11. Evaluate \(\sum_{k=0}^{h} 3^k\) exactly and as \(\Theta\).

C. Cases

12. Define worst/best/average for finding the maximum in an unsorted array of \(n\) elements (comparisons).
    
13. Binary search comparisons: worst-case \(\Theta(\log n)\); best-case \(\Theta(1)\) if middle hits. Average under uniform is \(\Theta(\log n)\). Explain.
    
14. Why is average case meaningless without a distribution?

D. Amortized

15. Dynamic array doubling: show total copy cost over \(n\) appends is \(<2n\).
    
16. What if we resize by \(+1\) each time capacity is full? Total cost of \(n\) appends?
    
17. What if we resize by \(\times 3\) instead of \(\times 2\)? Still amortized \(O(1)\)?
    
18. Explain in prose: amortized \(\neq\) average-case probability.
    
19. Aggregate method: if \(n\) ops cost \(\le 5n+100\), amortized cost?

E. Stretch

20. Analyze:

for i=1..n:
  for j=1..i:
    for k=1..j:
        O(1)

21. Loop \(i=1..n\) with \(O(i^2)\) work: total?
    
22. Show \(\sum_{i=1}^n \lfloor n/i\rfloor =\Theta(n\log n)\).
    
23. Potential idea (optional): \(\Phi=\text{size}\), show amortized append \(O(1)\) for doubling with a potential argument outline.
    
24. CS literacy: name two structures beyond arrays that use amortized \(O(1)\) stories (e.g. union-find ackermann, splay trees — names only).

---

Deep dive — sum bounds toolkit

Goal	Technique
Exact	Closed form (\(\sum i\), geometric)
\(\Theta\) only	Sandwich \(c_1 n^{k+1}\le\sum i^k\le c_2 n^{k+1}\)
Harmonic	Integral of \(1/x\)
Decreasing \(f\)	\(\int_1^{n+1} f\le\sum_{1}^n f\le f(1)+\int_1^n f\)

Example proof that \(\sum_{i=1}^n i=\Theta(n^2)\) without formula:
\(\sum_{i=\lceil n/2\rceil}^n i\ge (n/2)\cdot(n/2)=n^2/4\), and \(\sum_{i=1}^n i\le n\cdot n=n^2\).

---

Deep dive — amortized vs average vs worst

Concept	Adversary?	Randomness?	Bound type
Worst-case single op	Yes	No	per operation
Average-case	Distribution on inputs	Yes	expectation
Amortized	Worst sequence	No	average over sequence of ops

Dynamic array: a single append can be \(\Theta(n)\) worst-case, but amortized \(O(1)\), and there is no probability required.

---

Additional worked examples

Example 11 — Harmonic nested.
\(\sum_{i=1}^n\lfloor n/i\rfloor\): for each \(i\), about \(n/i\) multiples; total \(\Theta(n\log n)\).

Example 12 — Geometric outer.
\(i=1,2,4,\ldots,2^k\le n\), work \(O(n)\) each: \(O(n\log n)\) iterations count.

Example 13 — Resize +1 disaster.
Appending \(n\) times with capacity growth \(+1\): copy costs \(1+2+\cdots+n=\Theta(n^2)\).

Example 14 — Average search.
Unsuccessful search in unordered list always \(\Theta(n)\); successful uniform: \((n+1)/2\).

Example 15 — Triple dependent.
\(\sum_{i=1}^n\sum_{j=1}^i\sum_{k=1}^j 1=\sum_i\sum_j j=\sum_i j(j+1)/2=\Theta(n^3)\).

---

More exercises

25. Bound \(\sum_{i=1}^n\sqrt{i}\) as \(\Theta(n^{3/2})\) via integrals.
    
26. Analyze:

s=0
for i=1..n:
  for j=1..n:
    if j % i == 0: s++

27. Amortized: \(n\) ops, total cost \(n\log n\) — amortized cost?
    
28. Best/worst for finding if array is sorted (comparisons).
    
29. Show doubling from capacity \(1\) to \(\ge n\) copies \(<2n\) elements total.
    
30. Loop \(i=n; i\ge 1; i=i//3\) with \(O(1)\) body: \(\Theta(\log n)\).
    
31. Explain why average-case quicksort \(\Theta(n\log n)\) is not an amortized claim.
    
32. CS literacy: name one structure with expensive occasional rebuild amortized away.

---

Selected mini-solutions

1. \(n^2\).
   
2. \(n(n+1)/2=\Theta(n^2)\).
   
3. \(\ln(n+1)\le H_n\le 1+\ln n\).
   
4. Copies \(1+2+4+\cdots+2^{k}<2^{k+1}\le 2n\).
   
5. \(+1\) growth: \(\Theta(n^2)\) total.

---

Common pitfalls

Pitfall	Fix
Multiplying loop bounds always	Dependent bounds need careful sums
\(\sum_{i=1}^n i = O(n)\)	No: \(\Theta(n^2)\)
Worst-case of each op × \(n\)	May overcount; consider amortized
Average without model	State distribution
Integral bounds as exact equality	They sandwich
Calling amortized “expected”	No probability required

---

Checkpoint

• Can translate nested loops to sums
  
• Know \(\sum i\), \(\sum i^2\), \(H_n\), geometric sums
  
• Can set up best/worst/average
  
• Can prove amortized \(O(1)\) append for doubling arrays
  
• Exercises A–D done

Two personal takeaways:

1. …
   
2. …

Tomorrow

Day 84 — Master theorem and recursion trees.