-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?

Improve this question
4
  • Sounds like merge sort. Commented 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. Commented 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 Commented Nov 20, 2015 at 17:34
  • The solution should be: O(log 0,95(2/n)), how do I get that ? Commented Nov 20, 2015 at 18:05

1 Answer 1

Reset to default
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.

Improve this answer

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.