
Limits of Computation ◾ 301
Figure10.4 contains a table that analyzes these counts in more detail.
is table shows the count of tickets that require examination for ticket
stacks of size 0, 10, 20, and 30 tickets. e bottom table row is a useful
generalization that shows the count based upon a variable (N) number of
tickets. In other words, given a stack of N tickets, no matter of the value of
N, the number of examinations will be either N or N/2.
Regardless of whether the stack contains the winning ticket, we con-
clude that the performance of this kind of search algorithm is directly pro-
portional to the number of tickets in the stack ...