1
$\begingroup$

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?

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

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

$\endgroup$
  • 2
    $\begingroup$ 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). $\endgroup$ – Kevin Oct 16 '12 at 16:31
  • $\begingroup$ ^ Exactly. That is the proper big-o runtime $\endgroup$ – AK4749 Oct 16 '12 at 16:32
  • $\begingroup$ @Kevin you are right - I had overlooked the initialization x=0 ... $\endgroup$ – coproc Oct 16 '12 at 16:34
  • $\begingroup$ @coproc what do you mean by ld(y)? I've never heard of ld() before, so could you please explain a bit further? $\endgroup$ – Lost Oct 16 '12 at 18:05
  • $\begingroup$ @Lost ld is the "logarithmus dualis", the logarithm with base two. In other words: z = ld(y) is equivalent to 2^z = y $\endgroup$ – coproc Oct 16 '12 at 18:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy