Each element is touched a constant times
Updated
Linear two-pointer means each index is read O(1) times: once by i, maybe once more by a write at w, or once by L and never again after L passes it. Fast in Floyd may visit a node twice, still O(1) per node amortized O(n) total.
What to focus on
If an inner loop re-reads a suffix from scratch for every i without sliding, some elements are touched Θ(n) times each. That is the quadratic case.
Worked examples
compact
a = [0, 1, 0, 9]- each i read once
- indices 0 and 1 written once
Result: ≤ 2 touches each
inward
a = [1, 4, 9], t=13- index 0 read once then L passes it
- 2 and 1 read at the hit
Result: O(1) per index
nested re-read
a = [1, 4, 9], for each i rescan j=i+1..n-1- 9 is read from i=0 and i=1
- Θ(n) reads of the tail
Result: not constant touches
Try it
Write countReads(a). a is an array of integers. Two-sum a is sorted. Count how many times each index is read. Print the read counter for compact and two-sum, then reads of 9 in nested i<j. Return nothing. Compact on [0, 1, 0, 9]. Two-sum on [1, 4, 9]. Nested i<j on [1, 4, 9].
a is nonempty. Two-sum a is sorted non-decreasing, length ≥ 2.