My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum


Reply
 
LinkBack Thread Tools Display Modes
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




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.
restin84 is offline  
 
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.
Pueo is offline  
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.
restin84 is offline  
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)
Pueo is offline  
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?
restin84 is offline  
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 , so the probability it is not last is , or .

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 .
Pueo is offline  
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 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 .
Okay that makes perfect sense. Thank you. Sometimes I miss the little details.
restin84 is offline  
Reply

  My Math Forum > Science Forums > Computer Science

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 07:44 AM
Number of comparisons in insertion sort nicnicman Number Theory 2 December 21st, 2012 12:36 PM
find the expected number 450081592 Advanced Statistics 0 November 25th, 2011 08:16 PM
number of comparisons sangfroid Computer Science 2 November 6th, 2007 04:05 PM
Expected number of trials until success. hales Algebra 2 September 20th, 2007 08:16 AM





Copyright © 2018 My Math Forum. All rights reserved.