Determining big oh

[DylsexicChciken]

I just need help verifying that I have the correct analyses to the problem below:

 

Assume we have a random number generator function called randInt(i, j), which generates a random number between i and j. We will use this function to randomly generate a number between 1 and N, i.e., randInt(1, N).

 

We want to fill an N-sized array with a random permutation of the first N integers using the randInt function above.

 

Algorithm 1 :

Fill array arr_ from arr_[0] to arr_[N-1]. To do this, randomly generate numbers until you get a number that isn't contained in any of the filled slots of arr_. This ensures that all numbers from 0 to N is used.

 

My analyses:

My analysis says this algorithm has a probability, albeit extremely minute, that it will never terminate, so is this O(infinity)? This is because you can randomly generate a number that is already contained in the filled slots of arr_ every single time.

 

After summation algebra, I find the expected run time to be O(N^2).

 

Algorithm 2:

This time we use an extra array. This array is an array of type bool, so each value is either 1 or 0. This array, which we can call contains_, is also of size N. If we randomly generate a number X, then we set contains_[X] to true, so the next time we see a randomly generated number and it turns out to be X, we don't actually have to check all of the filled slots of arr_ to know if arr_ already contains X, we merely check to see if contains_[X] is set to true.

 

My analyses:

This algorithm suffers the same problem as algorithm 1, in that you can randomly generate a number that is already contained in the filled slots of arr_ every single time. So O(infinity), albeit there is no longer a need for a checking loop to check for contains as it was in algorithm 1.

 

Expected runtime = worst case run time = O(N).

 

Algorithm 3:

Fill the array one by one sequentially with 1, 2, 3, 4, ... , N. Then for each position arr_[ i ], swap it with a randomly generated location between 0 and i.

e.g.,

for( i = 1; i < n; ++i )
swap( a[ i ], a[ randInt( 0, i ) ] );

 

My analyses:

This has O(N) since the problem size is assuredly reduced by one each iteration, so it surely will reach N at some point unlike the last two problems.

 

Are my analyses correct?

Edited March 17, 2015 by DylsexicChciken

[Alicia1980]

Hi,

 

I guess your reasoning is correct. I only have a few remarks:

 

+ Algorithm 1: "from 0 to N is used" --> "from 1 to N are used"

 

+ Analysis of Algorithm 1: I think you are right in concluding that it's "O(infinity)". My hunch is that your instructor should have mentioned that the sequence a a a a ... a (ad infinitum) cannot arise, even though this sequence is as random as any other. If you may assume this, then O(N^2) holds but only under the additional assumption that O(randInt(...)) is O(1).

 

This discussion reminds me of Donald Knuth's recent remark that big-oh notation is often used incorrectly, also by a large part of the academic community. See chapter 3 in Knuth's latest book:

 

+ Knuth, Daylight, "Algorithmic Barriers Falling: P = NP?", Lonely Scholar, November 2014: www.lonelyscholar.com

 

best wishes,

Alicia

Edited March 17, 2015 by Alicia1980

[DylsexicChciken]

I just need help verifying that I have the correct analyses to the problem below:

 

Assume we have a random number generator function called randInt(i, j), which generates a random number between i and j. We will use this function to randomly generate a number between 1 and N, i.e., randInt(1, N).

 

We want to fill an N-sized array with a random permutation of the first N integers using the randInt function above.

 

Algorithm 1 :

Fill array arr_ from arr_[0] to arr_[N-1]. To do this, randomly generate numbers until you get a number that isn't contained in any of the filled slots of arr_. This ensures that all numbers from 0 to N is used.

 

My analyses:

My analysis says this algorithm has a probability, albeit extremely minute, that it will never terminate, so is this O(infinity)? This is because you can randomly generate a number that is already contained in the filled slots of arr_ every single time.

 

After summation algebra, I find the expected run time to be O(N^2).

 

Algorithm 2:

This time we use an extra array. This array is an array of type bool, so each value is either 1 or 0. This array, which we can call contains_, is also of size N. If we randomly generate a number X, then we set contains_[X] to true, so the next time we see a randomly generated number and it turns out to be X, we don't actually have to check all of the filled slots of arr_ to know if arr_ already contains X, we merely check to see if contains_[X] is set to true.

 

My analyses:

This algorithm suffers the same problem as algorithm 1, in that you can randomly generate a number that is already contained in the filled slots of arr_ every single time. So O(infinity), albeit there is no longer a need for a checking loop to check for contains as it was in algorithm 1.

 

Expected runtime = worst case run time = O(N).

 

Algorithm 3:

Fill the array one by one sequentially with 1, 2, 3, 4, ... , N. Then for each position arr_[ i ], swap it with a randomly generated location between 0 and i.

e.g.,

for( i = 1; i < n; ++i )

swap( a[ i ], a[ randInt( 0, i ) ] );

 

My analyses:

This has O(N) since the problem size is assuredly reduced by one each iteration, so it surely will reach N at some point unlike the last two problems.

 

Are my analyses correct?

 

EDIT: Expected run time = worst case rune time = O(N) for algorithm 3 not algorithm 2. I meant to copy and paste it for algorithm 3 but accidentally pasted it in algorithm 2.

Sorry, I made a wrong edit yesterday. But now I can't edit anymore, so here is the edited version:

 

 

I just need help verifying that I have the correct analyses to the problem below:

 

Assume we have a random number generator function called randInt(i, j), which generates a random number between i and j. We will use this function to randomly generate a number between 1 and N, i.e., randInt(1, N).

 

We want to fill an N-sized array with a random permutation of the first N integers using the randInt function above. We only want the run time analyses for the algorithms below:

 

Algorithm 1 :

Fill array arr_ from arr_[0] to arr_[N-1]. To do this, randomly generate numbers until you get a number that isn't contained in any of the filled slots of arr_. This ensures that all numbers from 0 to N is used.

 

My analyses:

My analysis says this algorithm has a probability, albeit extremely minute, that it will never terminate, so is this O(infinity)? This is because you can randomly generate a number that is already contained in the filled slots of arr_ every single time.

 

After summation algebra, I find the expected run time to be O(N^2).

 

Algorithm 2:

This time we use an extra array. This array is an array of type bool, so each value is either 1 or 0. This array, which we can call contains_, is also of size N. If we randomly generate a number X, then we set contains_[X] to true, so the next time we see a randomly generated number and it turns out to be X, we don't actually have to check all of the filled slots of arr_ to know if arr_ already contains X, we merely check to see if contains_[X] is set to true.

 

My analyses:

This algorithm suffers the same problem as algorithm 1, in that you can randomly generate a number that is already contained in the filled slots of arr_ every single time. So O(infinity), albeit there is no longer a need for a checking loop to check for contains as it was in algorithm 1.

 

Expected runtime = O(N).

 

Algorithm 3:

Fill the array one by one sequentially with 1, 2, 3, 4, ... , N. Then for each position arr_[ i ], swap it with a randomly generated location between 0 and i.

e.g.,

for( i = 1; i < n; ++i )

swap( a[ i ], a[ randInt( 0, i ) ] );

 

My analyses:

This has O(N) since the problem size is assuredly reduced by one each iteration, so it surely will reach N at some point unlike the last two problems.

 

Expected run time = worst case rune time = O(N)

 

Are my analyses correct?

Edited March 17, 2015 by DylsexicChciken