How to calculate the order of an algorithm with recursive calls inside a loop

Question

I have been doing some examples of calculating the cost recursive algorithms which are inside loops, and this one has me wondering how I could calculate it.

int example(int max) {
    int i  =  1;
    double x  =  0.0;

    while ( i <= max ) {
        x  =  calculate (x , i);
        i  = 2 ∗ i ;
    }
}

We know that calculate (int x, int i) is of O(i), and that the order of example should be based on max.

An easier example of this would be the same code with a for(int i = 1; i <= max; i++) loop, which would make an order on example of O(max^2), but in this case i is multiplied by two on each call. How could the cost be calculated in this case?

Answer 1

while loop will run in log(max). Each iteration of the loop will run in O(i). Hence, the total time complexity is:

T(max) = O(1 + 2 + 2^2 + ... + 2^{log(max)}) = O(2^{log(max) + 1} - 1)

As we know that 2^{log(max)} = max, T(max) = Theta(max).