My Math Forum Expected number of comparisons in an algorithm

 Computer Science Computer Science Forum

 October 11th, 2012, 10: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,...,n-1 (they are all distinct) input: a[0,....,n-1] 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 $x_i= 1 \text{ if } a[i] < mn \text{ and } 0 \text{ otherwise(we will have two comparisons every time } x_i= 1)$ $y_j= 1 \text{ if } a[i] > mx \text{ and } 0 \text{ otherwise }=$ $Pr(x_i= 1) = \frac{1}{2} \text{ and } Pr(y_j = 1) = \frac{1}{2}$ Define two more random variables $Y= \text{ number of 1 comparisons}$ $X= \text{ number of 2 comparisons}$ $E[TotalComparisons]= 2E[X] + E[Y]$ $= 2\sum_{i = 1}^{n-1}E[x_i] + \sum_{j = 1}^{n-1}E[y_j]$ $=2\sum_{i = 1}^{n-1}(Pr(x_i) = 1) + \sum_{j = 1}^{n-1}(Pr(y_i) = 1)$ $=2\sum_{i = 1}^{n-1}\frac{1}{2} + \sum_{j = 1}^{n-1}\frac{1}{2}$ $=n -1 + \frac{1}{2}(n-1) = \frac{3n-2}{2}$ 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, 07: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 if-statements. Thus, in your statements ........................if a[i] > mx: ................................mx = a[i] the comparison is a[i] > mx, and will be made every time the if-statement is executed. Thus the number of comparisons in the code you provide will be 2*(n-1), since every time through the loop both if-statements are executed, and the loop is executed n-1 times. However, I assume that the code you are asking about may be closer to input: a[0,....,n-1] 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 n-1 times. The problem thus seems to be how to determine how many times the first comparison fails.
October 13th, 2012, 09:39 AM   #3
Member

Joined: Sep 2009

Posts: 71
Thanks: 0

Re: Expected number of comparisons in an algorithm

Quote:
 Originally Posted by Pueo However, I assume that the code you are asking about may be closer to input: a[0,....,n-1] 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 n-1 times. The problem thus seems to be how to determine how many times the first comparison fails.
Yes that is right. I did put "if" as opposed to "else if". I made the correction to the original post.

 October 13th, 2012, 04: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 (n-1)/n. In the last time through the loop. Thus there will be 1 + (n-1)/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 (n-1)/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 (n-1)/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 + (n-1)/n) Summing up all the initial 1's, we get (n-1) + (1/2 + 2/3 +3/4 ... (n-1)/n)
October 14th, 2012, 11:25 AM   #5
Member

Joined: Sep 2009

Posts: 71
Thanks: 0

Re: Expected number of comparisons in an algorithm

Quote:
 Originally Posted by Pueo 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 (n-1)/n. In the last time through the loop. Thus there will be 1 + (n-1)/n comparisons for that iteration, plus all of the comparisons from previous iterations.
Just so I can attempt to understand better. We are saying the probability that the largest entry is not last is 1 - [the probability that the largest entry is last] = (n-1)/n.

Now the total number of comparisons = [1 comparison when the last entry is maximum] OR [(n-1)/n comparisons when the last entry is not maximum]
= 1 + (n-1)/n

Is this right?

October 14th, 2012, 01:56 PM   #6
Member

Joined: Oct 2009
From: Northern Virginia

Posts: 31
Thanks: 1

Re: Expected number of comparisons in an algorithm

Quote:
 Just so I can attempt to understand better. We are saying the probability that the largest entry is not last is 1 - [the probability that the largest entry is last] = (n-1)/n. Now the total number of comparisons = [1 comparison when the last entry is maximum] OR [(n-1)/n comparisons when the last entry is not maximum] = 1 + (n-1)/n Is this right?
As to the first statement, yes. The probability of the largest element is last is $\frac{1}{n}$, so the probability it is not last is $1 - \frac{1}{n}$, or $\frac{n-1}{n}$.

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 $\frac{1}{n}$ and the probability that it is not maximum is $\frac{n-1}{n}$, the way I would say it is the total number of comparisons is $1\times\frac{1}{n} + 2\times\frac{n-1}{n}$, which simplifies to $1 + \frac{n-1}{n}$.

October 14th, 2012, 02:17 PM   #7
Member

Joined: Sep 2009

Posts: 71
Thanks: 0

Re: Expected number of comparisons in an algorithm

Quote:
Originally Posted by Pueo
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 $\frac{1}{n}$ and the probability that it is not maximum is $\frac{n-1}{n}$, the way I would say it is the total number of comparisons is $1\times\frac{1}{n} + 2\times\frac{n-1}{n}$, which simplifies to $1 + \frac{n-1}{n}$.
Okay that makes perfect sense. Thank you. Sometimes I miss the little details.

 Tags algorithm, comparisons, expected, number

,

expected number of comparisons

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post pavankumar.thati Advanced Statistics 2 June 12th, 2013 07:44 AM nicnicman Number Theory 2 December 21st, 2012 12:36 PM 450081592 Advanced Statistics 0 November 25th, 2011 08:16 PM sangfroid Computer Science 2 November 6th, 2007 04:05 PM hales Algebra 2 September 20th, 2007 08:16 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top