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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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;


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|cite|improve this question

migrated from Oct 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)$.

share|cite|improve this answer
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

Your Answer


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