Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

migrated from stackoverflow.com Oct 17 '12 at 17:34

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

1 Answer

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)$.

share|improve this answer
2  
It looks to me like the first loop has y iterations, so it would be O(y), which is dominant over O(ld(y)), so the overall complexity would be O(y). –  Kevin Oct 16 '12 at 16:31
    
^ Exactly. That is the proper big-o runtime –  AK4749 Oct 16 '12 at 16:32
    
@Kevin you are right - I had overlooked the initialization x=0 ... –  coproc Oct 16 '12 at 16:34
    
@coproc what do you mean by ld(y)? I've never heard of ld() before, so could you please explain a bit further? –  Lost Oct 16 '12 at 18:05
    
@Lost ld is the "logarithmus dualis", the logarithm with base two. In other words: z = ld(y) is equivalent to 2^z = y –  coproc Oct 16 '12 at 18:48
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.