sec adversarial lower bounds proofs how many assignments that largest must do function largest might do an assignment on any iteration of the for loop because this event does happenor does not happenif we are given no information about distribution we could guess that an assignment is made after each comparison with probability of one half but this is clearly wrong in factlargest does an assignment on the ith iteration if and only if [iis the biggest of the the first elements assuming all permutations are equally likelythe probability of this being true is / thusthe average number of assignments done is = = which is the harmonic series hn hn th(log nmore exactlyhn is close to loge how "reliableis this averagethat ishow much will given run of the program deviate from the mean costaccording to cebysev' inequalityan observation will fall within two standard deviations of the mean at least of the time for largestthe variance is loge the standard deviation is thus about logepn so of the observations are between loge loge and loge loge is this narrow spread or wide spreadcompared to the mean valuethis spread is pretty widemeaning that the number of assignments varies widely from run to run of the program hn adversarial lower bounds proofs our next problem will be finding the second largest in collection of objects consider what happens in standard single-elimination tournament even if we assume that the "bestteam wins in every gameis the second best the one who loses in the finalsnot necessarily we might expect that the second best must lose to the bestbut they might meet at any time let us go through our standard "algorithm for finding algorithmsby first proposing an algorithmthen lower boundand seeing if they match unlike our analysis for most problemsthis time we are going to count the exact number of comparisons involved and attempt to minimize them simple algorithm for finding the second largest is to first find the maximum (in comparisons)discard itand then find the maximum of the remaining elements (in comparisons