-3

I have been asked the following question..

An algorithm considers n elements, sorts 5% of n out, considers the remain elements(95%), sorts 5% of the remain elements, and so on until finally one last element is left. Which complexity does the algorithm have and why?

4
  • Sounds like merge sort. Nov 20, 2015 at 16:59
  • @LawrenceAiello no more like quick sort where instead of grabbing the median for pivot you grab the 5th percentile. Nov 20, 2015 at 17:01
  • Sharing your research helps everyone. Tell us what you've tried and why it didn’t meet your needs. This demonstrates that you’ve taken the time to try to help yourself, it saves us from reiterating obvious answers, and most of all it helps you get a more specific and relevant answer. Also see How to Ask
    – gnat
    Nov 20, 2015 at 17:34
  • The solution should be: O(log 0,95(2/n)), how do I get that ?
    – Luka Peric
    Nov 20, 2015 at 18:05

1 Answer 1

0

Big O time complexity of divide and conquer algorithms is not affected by what fraction you divide things into. This is because logs of different bases differ by only a constant factor. So the Big O time complexity in your case is the same as if you separate 50% out.

So you should get the usual nLogn sort.

Not the answer you're looking for? Browse other questions tagged or ask your own question.