Java. Rank the three algorithms in terms of expected running time (for large n)

Question

Java. Rank the three algorithms in terms of expected running time (for large n) and give an explanation to justify your ranking. Thank you!

Suppose you need to generate a random permutation of the first N integers For example, 14, 3, 1, 52) and {3, 1, 4, 2, 5} are legal permutations, but [5, 4, 1, 2, 1 is not, because one number () is duplicated and another (3) is missing. This routine is often used in simulation of algorithms. We assume the exis- tence of a random number generator, r, with method randInt (i, j), that generates integers between i and j with equal probability. Here are three algorithms 1. Fill the array a from a[O] to a[n-1 as follows: To fill ai], generate random numbers until you get one that is not already in a [0], a[i],... , ali-1] 2. Same as algorithm (1), but keep an extra array called the used array. When a random number, ran, is first put in the array a, set used [ran] - true. This means that when filling ali] with a random number, you can test in one step to see whether the random number has been used, instead of the (possibly) i steps in the first algorithm. 3. Fill the array such that a[i] = i + 1 . Then for( i = 1; i

Explanation / Answer

1. In this alogorithm the loop is running from 1..n to generate n random numbers but also
   we need to serach the element in the array made so far to avoid duplication. So
   for every i there is a loop runninh up to i-1. So
   for i = 0 Search loop will run 0 times
       i = 1 Search loop will run 1 times
       i = 2 Search loop will run 2 times
       i = n Search loop = nwill run n times

      So the total complexity will be
      adding all the search loops as generation is a constant step operation.
      Also we need to repeat the genration againg if it is a duplicate but we
      have ignored that conplexity as searching is a major activity here
       = 0+1+2+3+...+n)      (it is just sumof first n natural numbers which is n(n=1)/2
       = n(n+1)/2 = n/2 + n^2/2 So the compexity is O(n^2)

2. Here finding the duplicat is a single step processing because we just need
   to check Used[random nuber] = true or not. So here we are generating a number
   checking the duplication in a single step .We are generating n random numbers
   so here the loop is running from 1..n. So the complexity of this will be O(n)

3. In this also there is a loop running for 1..n and swapping is the constant opeartion
   So in this case also the complexity is of O(n)

   Ranking wise first rank will be given to Third alorithm (as complexity is low and there is no extra space required as in the case of second algorith)

    Second rank will be given to second alorithm because of less complexity but space requirement
   is their.

    Last rank will be given to the first algorithm as its complexity is very high as compared
    to second and third algorithm but there is no extra space requirement.

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.