c. Find the worst case runtime (big-O notation) for BogoSort, pseudocode is give

Question

c. Find the worst case runtime (big-O notation) for BogoSort, pseudocode is given below Please Note that the answer is not O(n):  

procedure BogoSort(array A)                      

     while not isInOrder(A):                               

                shuffle(A)

shuffle() randomly reorders A. isInOrder() returns true if the list is in order, false otherwise. It has the following pseudocode:

procedure isInOrder(array A, length(A) = n)                         

       for i in 0 to n-1                                                                          

             if A[i] > A[i+1]                                 

                 return false

I

Explanation / Answer

procedure BogoSort(array A)                      

     while not isInOrder(A): ====> WE CAN SEE THAT isInOrder , check if its ordered or not and checks in O(n) time   

                shuffle(A) ==> This will shuffle randomly in permutaion , there are n! permutation for n numbers

We know that in n numbers there exists n! permutaion , It mat so happen that Shuffle will do permutaion n! times and each time we call isInOrder and that takes n time

Overall time complexity is n*n! => O(n*n!) and that corresponds to Worst case

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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