I have two for loops, one nested within the other. I have two int variables n and U, where U > n. I know that the outer loop runs exactly U times (pretty much for(int i = 0; i < U -1; i++)), and the inner loop runs exactly n times in total for the duration of the entire execution. It can run n times once and never run again, or it can run once in each iteration of the outer loop n times, or anything in between.

It's obvious that this runs in O(nU) time. However, I think I can also state it runs in theta(U + n) time because the inner loop runs independently of the outer one. But still, they are nested, and not multiplying the runtimes of nested loops feels awkward.

Intuitively I know I am right, but I don't really know how to show it. I'm not looking for a formal proof, but any kind of insight is welcome.


Yes, the running time is $O(U+n)$, assuming that each iteration of the inner loop takes $O(1)$ time. The way to prove it: try to write down an expression for the running time, as a function of $U$ and $n$. What did you get? Now, see you can show that this expression is at most $c \cdot (U+n)$, for some constant $c$ that you get to specify.

| cite | improve this answer | |

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.