# 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?

• 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