
Computer Science Computer Science Forum 
 LinkBack  Thread Tools  Display Modes 
October 11th, 2012, 11:12 AM  #1 
Member Joined: Sep 2009 Posts: 71 Thanks: 0  Expected number of comparisons in an algorithm
I have a question(and possible solution) for an algorithms course... given the following algorithm, provide an exact calculation for the expected number of total comparisons made by the algorithm when the given array contains a random permutation of the numbers 0,1,...,n1 (they are all distinct) input: a[0,....,n1] output: (max, min) pair max_min(a) ........mx = a[0] ........ mn = a[0] ................for i = 1 to length(a) do ........................if a[i] > mx: ................................mx = a[i] ........................else if a[i] < mn: ................................mn = a[i] return(mx,mn) Define two indicator random variables Define two more random variables Not sure if this is right. I wanted to see if I am on the right track or in the general area of obtaining a solution. Any advice would be appreciated. 
October 13th, 2012, 08:50 AM  #2 
Member Joined: Oct 2009 From: Northern Virginia Posts: 31 Thanks: 1  Re: Expected number of comparisons in an algorithm
As no one else has jumped in, I'll give it a go with what I hope is a helpful hint... The comparisons are made in the ifstatements. Thus, in your statements ........................if a[i] > mx: ................................mx = a[i] the comparison is a[i] > mx, and will be made every time the ifstatement is executed. Thus the number of comparisons in the code you provide will be 2*(n1), since every time through the loop both ifstatements are executed, and the loop is executed n1 times. However, I assume that the code you are asking about may be closer to input: a[0,....,n1] output: (max, min) pair max_min(a) ........mx = a[0] ........mn = a[0] ................for i = 1 to length(a)1 do ........................if a[i] > mx: ................................mx = a[i] ........................elseif a[i] < mn: ................................mn = a[i] return(mx,mn) where the second comparison is made only if the first comparison fails. The first comparison, with mx, is executed every time the loop is, so n1 times. The problem thus seems to be how to determine how many times the first comparison fails. 
October 13th, 2012, 10:39 AM  #3  
Member Joined: Sep 2009 Posts: 71 Thanks: 0  Re: Expected number of comparisons in an algorithm Quote:
 
October 13th, 2012, 05:43 PM  #4 
Member Joined: Oct 2009 From: Northern Virginia Posts: 31 Thanks: 1  Re: Expected number of comparisons in an algorithm
As the program loops through the array, when the index = i, mx is the largest so far, and the comparison will succeed when the next one, a[i] is larger than any of the previous entries. For an array of size n, the probability that the largest entry is is the last position is 1/n, since any of the positions are equally likely. So the probability that the largest entry is NOT last is (n1)/n. In the last time through the loop. Thus there will be 1 + (n1)/n comparisons for that iteration, plus all of the comparisons from previous iterations. Now consider an array of size 1. The comparisons are never made. For an array of size 2, the number of comparisons made is 1 (the comparison with mx), which will fail (n1)/n, or 1/2, of the time. Thus the average number of comparisons for this step will be (1 + 1/2), for a total of(1 + 1/2). For an array of size three, the number of comparisons made is 1 (again, the comparison with mx), and (n1)/n = 2/3. Thus for the last comparison only, the number of expected comparisons is (1 + 2/3). But to reach this point there has already been (1 + 1/2) comparisons from the previous time through the loop. So for n = 3, the number of comparisons is (1 + 1/2) + (1 + 2/3). And so on. The number of comparisons for an array of size n is thus (1 + 1/2) + (1 + 2/3) + (1 + 3/4) + ... (1 + (n1)/n) Summing up all the initial 1's, we get (n1) + (1/2 + 2/3 +3/4 ... (n1)/n) 
October 14th, 2012, 12:25 PM  #5  
Member Joined: Sep 2009 Posts: 71 Thanks: 0  Re: Expected number of comparisons in an algorithm Quote:
Now the total number of comparisons = [1 comparison when the last entry is maximum] OR [(n1)/n comparisons when the last entry is not maximum] = 1 + (n1)/n Is this right?  
October 14th, 2012, 02:56 PM  #6  
Member Joined: Oct 2009 From: Northern Virginia Posts: 31 Thanks: 1  Re: Expected number of comparisons in an algorithm Quote:
The second I am not sure about. The total number of comparisons is 1 when the last entry is maximum, and 2 when the last entry is not maximum. Since the probability that the last element is maximum is and the probability that it is not maximum is , the way I would say it is the total number of comparisons is , which simplifies to .  
October 14th, 2012, 03:17 PM  #7  
Member Joined: Sep 2009 Posts: 71 Thanks: 0  Re: Expected number of comparisons in an algorithm Quote:
 

Tags 
algorithm, comparisons, expected, number 
Search tags for this page 
Click on a term to search for related topics.

Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Expected number of children  pavankumar.thati  Advanced Statistics  2  June 12th, 2013 08:44 AM 
Number of comparisons in insertion sort  nicnicman  Number Theory  2  December 21st, 2012 01:36 PM 
find the expected number  450081592  Advanced Statistics  0  November 25th, 2011 09:16 PM 
number of comparisons  sangfroid  Computer Science  2  November 6th, 2007 05:05 PM 
Expected number of trials until success.  hales  Algebra  2  September 20th, 2007 09:16 AM 