1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Raphael Oct 30 '13 at 18:20
  • $\begingroup$ @Raphael I don't understand your question, can you clarify? $\endgroup$ – Edgar Aroutiounian Oct 30 '13 at 18:47
  • $\begingroup$ You talk about the "complexity" of the outer loop as if it would not contain the inner loop. $\endgroup$ – Raphael Oct 30 '13 at 19:51
3
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

Your second example is correct.

$\endgroup$
1
$\begingroup$

heres a very nice general/introductory online ref/chapter on the subj by an expert that will answer your question and give you a firm beginning foundation, with lots of exercises.

from his book free online

$\endgroup$
  • 1
    $\begingroup$ Much appreciated. $\endgroup$ – Edgar Aroutiounian Oct 30 '13 at 17:47
  • $\begingroup$ will sketch this out more carefully if there is more votes on your question. basically it depends on what is inside the loop. if it takes constant time inside the loop, your reasoning is correct. if something more complicated is happening, esp function calls, which can depend on input size, it requires more sophisticated analysis... $\endgroup$ – vzn Oct 30 '13 at 17:52

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.