Problem Detail: I have a task where i need to find a problem in which mergesort has to have a runtime of $O(n^2 log n)$. In our lecture we said that the runtime is $O(n log n)$ assuming that every comparison is $O(1)$. I think that I have to work with comparison-complexity but I dont know how to create a runtime of $O(n^2 log n)$ since mergesort has best and worst-case complexity of $O(n log n)$. Could anybody help me out creating a problem to achieve a runtime of $O(n^2 log n)$ ?
Asked By : thedude
Answered By : David Richerby
Remember what $O(cdot)$ means. You don’t need to do anything. Mergesort has a running time of $O(nlog n)$ which is already $O(n^2 log n)$, $O(2^n)$ and $O(text{any larger function you want})$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/42640 Ask a Question Download Related Notes/Documents
