hulk_baba's blog

Help with an Assignment problem with rigorous proof
By hulk_baba, history, 7 years ago, In English

Please see the image for 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.. 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..

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Part (a) is easy — For each i belongs to [1,k] you can binary search in O(logn) questions to find out how many numbers are <=i. Let this be f(i). Then print out f(i)-f(i-1) numbers equal to i. Time = O(klogn) trivially.

→ Reply