# Clarification about big Oh calculation

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? – Edgar Aroutiounian 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

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