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$
1
  • 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$
1
  • 2
    $\begingroup$ It's worth noting that the fractions .9 and .1 are immaterial, as long as they're nonzero. $\endgroup$ 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$
5
  • $\begingroup$ Shouldn't $m'$ be in the O(m''•n)? $\endgroup$
    – Evil
    Dec 3 '16 at 22:50
  • $\begingroup$ yes, my mistake $\endgroup$ Dec 4 '16 at 1:26
  • $\begingroup$ sorry, actually don't $\endgroup$ 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$ 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.