ZEAL TEST ALGORITHM

Question

Comments

The answer given is O(n^2) but how?

---

@NIL DAS

assume 5,4,3,2,1 is the array!

at each level the varition of merge sort is dividing it like this :

$L_o \ :$ {5,4,3,2,1}
$L_1 \ :$ {5}{4,3,2,1}
$L_2 \ :$ {5}{4}{3,2,1}
$L_3 \ :$ {5}{4}{3}{2,1}
$L_4 \ :$ {5}{4}{3}{2}{1}

number of level that are created are 5 and now at each level will sort element that is 5 elements ( i.e compare and swap) , so the total cost of operations will take 5 * 5 = 25 total operations to sort 

This question is similar to having the maximum or minimum element as the pivot in the Quick sort Algorithm.

hope this helps!

Answer 1

answer will be O(n^2)
see, for normal merge sort, we do T(n)=2T(n/2) + n, here n because comparing and mergin takes order of n time
now in this question, it will be T(N)=T(1) + T(n-1) + n
this will give us order of n^2
 

Comments

thanks