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

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

3 Answers 3

Reset to default
3
$\begingroup$

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

Improve this answer
$\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.

Improve this answer
$\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

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Much appreciated. $\endgroup$
    – c-o-d
    Commented Oct 30, 2013 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
    Commented Oct 30, 2013 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.