Help with an Assignment problem with rigorous proof

hulk_baba · February 7, 2017, 8:57pm

Please see below assignment problem :-

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…

vijju123 · February 7, 2017, 9:18pm

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

hulk_baba · February 7, 2017, 10:07pm

Sorry, it was really…silly :).

vijju123 · February 7, 2017, 10:37pm

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

hulk_baba · February 7, 2017, 10:44pm

really?? what is going through your mind…

parthdhar · February 8, 2017, 4:55pm

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).

hulk_baba · February 9, 2017, 4:36am

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

kelly567b · July 20, 2018, 4:38pm

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.