[Solved]: Theta Runtime of Nested for Loops

Problem Detail: 

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.

Asked By : Cem K.

Answered By : D.W.

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12995