0
$\begingroup$

We are given $m$ arrays of $n$ elements each. For 90% of these arrays we run an $\mathcal O(n)$ algorithm and for the other 10% an $\mathcal O(n\log n)$ algorithm. What is the total time complexity? I think it is $\mathcal O(m n \log n)$ but I am not sure.

$\endgroup$
  • 4
    $\begingroup$ Why do you think that? Without your thought process, we can't help you. $\endgroup$ – Raphael Dec 3 '16 at 19:50
1
$\begingroup$

The O(n log n) eventually grows faster than the O(n) algorithm. We always take the fastest growing component of the algorithm when deciding the complexity, so you're right that the total complexity of the algorithm is O(m n log(n))

$\endgroup$
  • 2
    $\begingroup$ It's worth noting that the fractions .9 and .1 are immaterial, as long as they're nonzero. $\endgroup$ – Rick Decker Dec 3 '16 at 18:37
-2
$\begingroup$

Ok, i dont speak English so i will be concise:

m * 90 / 100 = m'

m * 10 / 100 = m''

=> O(m'·n·log(n)) + O(m''·n) = O(m'·n·log(n) + m''·n)

=> O(m'·n·log(n))

$\endgroup$
  • $\begingroup$ Shouldn't $m'$ be in the O(m''•n)? $\endgroup$ – Evil Dec 3 '16 at 22:50
  • $\begingroup$ yes, my mistake $\endgroup$ – Juan Ignacio Sánchez Dec 4 '16 at 1:26
  • $\begingroup$ sorry, actually don't $\endgroup$ – Juan Ignacio Sánchez Dec 4 '16 at 1:28
  • 1
    $\begingroup$ I see a calculation, but no reasoning. $\endgroup$ – Raphael Dec 4 '16 at 2:05
  • $\begingroup$ Correct me then, please. $\endgroup$ – Juan Ignacio Sánchez Dec 4 '16 at 5:19

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.