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$
4
  • 1
    $\begingroup$ Hint: try to think of your input as not being necessarily a set of atomic objects. $\endgroup$ May 16, 2015 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, 2015 at 16:33
  • $\begingroup$ That would be a start. $\endgroup$ May 16, 2015 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, 2015 at 16:41

1 Answer 1

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$
3
  • $\begingroup$ what is O(⋅) specifically ? i see this notation for the first time (i want to google it) $\endgroup$
    – thedude
    May 16, 2015 at 17:05
  • $\begingroup$ Oh lol. Sorry but I thought the "dot" has a meaning. $\endgroup$
    – thedude
    May 16, 2015 at 17:08
  • 1
    $\begingroup$ Oh! It just stands for "something". :-) $\endgroup$ May 16, 2015 at 17:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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