Complexity of SHUFFLE (April Lunchtime)

general
, ,
1

Can anyone explain how the complexity of setter’s solution of SHUFFLE Problem (April Lunchtime)is this:
O(N+K∗log(N/K) or O(N*log(N))O(N∗log(N))

1 Like
2

link-SHUFFLE - Editorial

3

@zephxr Sir,basically what you do is you break up the whole array into k subarrays where in each subarray indexes of adjacent elements should differ by K.And then what we do is that we sort each one of those k arrays by taking those elements into some array,sorting them and again placing them back in original array.So this sorting will take N/K *log(N/K) for each f the K subarrays as each total number of elements in original array is N and we then assume that each such subarray as above contains N/K elements.
I hope this clears your doubt.
Feel free to ask again.

1 Like
5

Thank you so much @sayan_1999 for explaining it.Well, i understood it till the complexity of sorting the k subarrays and then merging them back which is N/K *log(N/K)
But how we reach to this final part : O(N+K∗log(N/K) or O(N*log(N))O(N∗log(N))

6

If you speak of the O(N*log(N)) then it is just the sorting complexity which is actually the worst case complexity which occurs when K=1.that’s it.

1 Like
7

No i was asking how we reach to this : O(N+K∗log(N/K)) @sayan_1999

8

Sir,I think this complexity comes from some kind of binary search they are performing on K subarrays.And then merging the K subarray takes O(N) time.

1 Like