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)$ ?
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ Hint: try to think of your input as not being necessarily a set of atomic objects. $\endgroup$– André Souza LemosMay 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$– thedudeMay 16, 2015 at 16:33
-
$\begingroup$ That would be a start. $\endgroup$– André Souza LemosMay 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$– thedudeMay 16, 2015 at 16:41
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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})$.
-
$\begingroup$ what is O(⋅) specifically ? i see this notation for the first time (i want to google it) $\endgroup$– thedudeMay 16, 2015 at 17:05
-
$\begingroup$ Oh lol. Sorry but I thought the "dot" has a meaning. $\endgroup$– thedudeMay 16, 2015 at 17:08
-
1$\begingroup$ Oh! It just stands for "something". :-) $\endgroup$ May 16, 2015 at 17:10