2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Hint: try to think of your input as not being necessarily a set of atomic objects. $\endgroup$ – André Souza Lemos May 16 '15 at 16:10
  • 1
    $\begingroup$ @AndréSouzaLemos so you mean if i take for instance vectors except of numbers than it will work ? $\endgroup$ – thedude May 16 '15 at 16:33
  • $\begingroup$ That would be a start. $\endgroup$ – André Souza Lemos May 16 '15 at 16:39
  • $\begingroup$ @AndréSouzaLemos thank you i did not think of this option ! i think that will help me a lot :-) $\endgroup$ – thedude May 16 '15 at 16:41
3
$\begingroup$

Remember what $O(\cdot)$ means. You don't need to do anything. Mergesort has a running time of $O(n\log n)$ which is already $O(n^2 \log n)$, $O(2^n)$ and $O(\text{any larger function you want})$.

$\endgroup$
  • $\begingroup$ what is O(⋅) specifically ? i see this notation for the first time (i want to google it) $\endgroup$ – thedude May 16 '15 at 17:05
  • $\begingroup$ Oh lol. Sorry but I thought the "dot" has a meaning. $\endgroup$ – thedude May 16 '15 at 17:08
  • 1
    $\begingroup$ Oh! It just stands for "something". :-) $\endgroup$ – David Richerby May 16 '15 at 17:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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