# Asymptotic time complexity of a two-loop program

I have two pieces of code in a function which I'm trying to calculate the asymptotic running time for:

for (int x = 0; x < y; x++) {
total  +=  total;
total  +=  x;
}


and:

while (y > 0) {
total  -=  y;
y  =  y/2;
}


Combining those two pieces of code, what is the run time of that function and how do I calculate it?

-

## migrated from stackoverflow.comOct 17 '12 at 17:34

This question came from our site for professional and enthusiast programmers.

what do you mean combining? combining how? How is y initialized? Is this homework? –  AK4749 Oct 16 '12 at 16:22
Do you want to measure the time or calculate a theoretical time ? –  Paul R Oct 16 '12 at 16:22
@PaulR tagged as Big-O, sounds like theoretical –  AK4749 Oct 16 '12 at 16:23
combining as in they're in the same function –  Lost Oct 16 '12 at 18:06

The first loop has $y$ iterations, each iteration takes constant time ($O(1)$), so all together we have $O(y)$. The second loop has $\log_2(y)$ iterations of constant time, giving a complexity of $O(\log_2(y))$. Both loops together we have: $O(y + \log_2(y)) = O(y)$ because $y$ dominates $\log_2(y)$.
@Kevin you are right - I had overlooked the initialization x=0 ... –  coproc Oct 16 '12 at 16:34