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.