Say you have a loop that iterates over an array,

for i in someArray:
//some code


This basic example would have a running time of $O(n)$. Say that you added a nested loop with equal number of operations, this then would be $O(n^2)$. My question is, is it safe to do this kind of simplication in general? For example,

Say your outer loop had worst case complexity of $O(n^2)$ and your inner loop has worst case complexity of $O(\log n)$. Can the total time complexity be said as $O(n^2\log n)$?

• Note that the outer loop subsumes (a multiple of) the runtime of the inner loop. Where does the logarithmic factor go? Is your language off?
– Raphael
Oct 30 '13 at 18:20
• @Raphael I don't understand your question, can you clarify? Oct 30 '13 at 18:47
• You talk about the "complexity" of the outer loop as if it would not contain the inner loop.
– Raphael
Oct 30 '13 at 19:51

Yes, that's correct. Big O is all about the upper bound on the number of executions of an algorithm.

Your first generalisation is wrong, it depends on what's the complexity of loop content. However if that 'some code' is of constant complexity [something like $O(1)$], the whole complexity will be $O(n)$.