what is the time complexity of this code? [closed]

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. Closed 11 years a开发者_如何转开发go.

int i = 1;
while (i < n/2)
{
    i = i * 2;
    int j = i;

    while (j > 1)
        --j;
}

---

O(n):
outer loop runs logn times, in each iteration: i=1,2,4,8,...n/4 (entrance values)
inner loops runs 2*i times (entrance values)
so at overall you get: 2+4+8+...+n/2 = n-2 = O(n)

---

The inner loop executes twice on the first iteration, then four times, then eight times, etc.

So you need to figure out where the sum terminates:

2 + 4 + 8 + ...

and then work out how to evaluate it (clue: geometric series).