##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
The amortized analysis
For fixed length , you compute for all where . Each cell searches from to . As increases, these ranges chain together: the right endpoint of one is the left endpoint of the next.
Example with , : cell searches . Cell searches . Cell searches . The ranges tile without overlap. Total checks per length: . Summing over lengths: .
