DylsexicChciken Posted March 17, 2015 Share Posted March 17, 2015 (edited) 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 Link to comment Share on other sites More sharing options...
Alicia1980 Posted March 17, 2015 Share Posted March 17, 2015 (edited) 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 1 Link to comment Share on other sites More sharing options...
DylsexicChciken Posted March 17, 2015 Author Share Posted March 17, 2015 (edited) 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 Link to comment Share on other sites More sharing options...
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now