ME test series

Question

Suppose that the partition algorithm of quick sort always produce a 9-to-1 proportional split. Then the Running time of algorithm over an unsorted array of n-elements is ____________________?

a) O(n2)                        b) O(nlogn)                     c) O(n)                        d) None

Answer 1

If we do split in that manner , then the recurrence relation will be :

       T(n)  =  T(9n / 10) + T(n / 10) + O(n)

where the first branch is of the size 9n/10 and second one is n/10 so branches have nodes in 9 : 1 ratio as mentioned in the question..

And O(n) as we know for partitioning algortihm..

So solving the above using recursion tree approach , we find that the cost at each level of tree which is given is n here ..Let us see how..

At 1st level , the cost = n

At 2nd level , the cost  = 9n / 10 + n / 10 = n

So cost will remain same at all levels..

So time complexity = Summation of cost of all levels

                             = O(n * log_10/9 n) if we take longer branch [T(9n / 10)] thus getting the upper bound

                             = Ω(n * log₁₀ n) which is the shorter branch 

But anyway base of logarithm does not matter as it is only a matter of constant..

Hence B) is the correct answer..

Answer 2

It will be B only , you can refer cormen it is clearly given

Comments

Thank you :)

Answer 3

B. O(nlogn)