# What is the Big O time complexity of this algorithm?

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.

– Raphael
Dec 3 '16 at 19:50

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

• It's worth noting that the fractions .9 and .1 are immaterial, as long as they're nonzero. Dec 3 '16 at 18:37

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

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