The following program determines the maximum value in an unordered array A[1...n] of distinct elements: 1....

 

Transcribed Image Text:

The following program determines the maximum value in an unordered array A[1...n] of distinct elements: 1. 2. 3. 4. 5. max-x for i=1 to n do compare A[i] to max if A[i]> max then max = = A[i] (a) If a number x is randomly chosen from a set of n distinct numbers, what is the probability that is the largest in that set? (b) When line 5 of the program is executed, what is the relationship between A[i] and A[j] for 1 ji? (c) For each i in the range 1 i n, what is the probability that line 5 is executed? (d) Let S, S2, ..., Sn be n random variables, where si represents the number of times (0 or 1) that line 5 is executed during the i-th iteration of the for-loop. What is E[si]? (e) Let s = 81 +82 +...+Sn be the total number of times that line 5 is executed during somendows run of the program. Prove that E[s] = O(logn). Go to Settings to activate The following program determines the maximum value in an unordered array A[1...n] of distinct elements: 1. 2. 3. 4. 5. max-x for i=1 to n do compare A[i] to max if A[i]> max then max = = A[i] (a) If a number x is randomly chosen from a set of n distinct numbers, what is the probability that is the largest in that set? (b) When line 5 of the program is executed, what is the relationship between A[i] and A[j] for 1 ji? (c) For each i in the range 1 i n, what is the probability that line 5 is executed? (d) Let S, S2, ..., Sn be n random variables, where si represents the number of times (0 or 1) that line 5 is executed during the i-th iteration of the for-loop. What is E[si]? (e) Let s = 81 +82 +...+Sn be the total number of times that line 5 is executed during somendows run of the program. Prove that E[s] = O(logn). Go to Settings to activate