Ace Question 10

Question

 

Comments

(C) nlogn/2 ??

---

Yes Please Explain

---

https://www.researchgate.net/publication/225952172_Bottom-up_mergesort_-_A_detailed_analysis

---

C. 

At every level, in best case, n/2n/2 comparisons and total lognlogn levels...Hence, nlogn/2

Answer 1

2-way bottom-up merge sort the last level (except original array) named as level-1, so on... and let n=2^k ===> only k levels present totally

if two sorted arrays have n1 and n2 elements ===> to merge them we require no.of comparissions

1) minimum = n1 

2) maximum = n1+n2-1

minimum no.of comparissions required for forming

level 1 :- $\frac{n}{2^{1}} $ . 1

level 2 :- $\frac{n}{2^{2}} $ . 2

level 3 :- $\frac{n}{2^{3}} $ . 4

.

.

.

.

 

level j :- $\frac{n}{2^{j}} $ . 2 ^j-1

 

Total Comparissions = $\sum_{j=1}^{k} \frac{n}{2^{j}}.2^{j-1}$ = $ \sum_{j=1}^{k} \frac{n}{2} $ = $  \frac{n}{2} \sum_{j=1}^{k} 1 $  = $  \frac{n}{2} (k) $ = $  \frac{n.log(n)}{2} $

Answer 2

when all the elements are in increasing order(1,2,3,4,5......n)

lets take example 1, 2, 3, 4, 5, 6, 7, 8  it only requires 12 comparisons.

in 1st level 1+1+1+1 = 4 comparisons

in 2nd level 2+2 = 4 comparisons

in 3rd level 4 comparisons

total 4+4+4 =12 comparisons which is (nlogn/2) C option.