Help with an Assignment problem with rigorous proof

Please see below assignment problem :-

img
I have idea of that this will be solved by divide and conquer but can’t figure out the exact way. Please suggest me some algorithm to do this. A proof is really welcome…

Not wanting to be a party spoiler but I don’t see any problem XD

1 Like

Sorry, it was really…silly :).

1 Like

This Q blew me up…*hides in a corner from this monstrous 20-question sorting algo"

really?? what is going through your mind…

You can use counting sort

For all numbes from 1...k, binary search (in Y/N questions) for the number of occurences of the particular number. Just write that number that many times. This would be O(k \log n).

3 Likes

Thank you. I got it later but not the name:)

I also had such problem. I found some additional information about binary search at AustralianWritings and this helped me. Just check it and maybe this will help you too.