Virtual Gate Test Series: Algorithms - Sorted List (Time Complexity)

Question

 my answer don't match any answer plz chec

Comments

@habibkhan @robert+Singh @Hradesh+patel

---

Change this to answer. Now u have got the point

---

@habibkhan Thanks

Answer 1

Let's assume $ k = 2^m $

Then to merge two lists of size n it takes  $ c_1 * n $ and there are $ k/2 $ such lists thus = $ c_1 * n * (k/2) $

Then to merge two lists of size 2n it takes  $ c_2* n $ and there are $ k/4 $ such lists thus = $ c_2 * n * (k/4) $

 - - - - - - - --  - - - -

Then to merge two lists of size $ 2^{m-1} $ it takes  $ c_{m-1}*n $ and there are $ k/2^{m-1} $ such lists thus = $ c_{m-1} * n * k/2^{m-1} $

if $ c_1 = c_2=------------=c_{m-1} $

thus total time = $ O(kn\log{k}) $