big o - Why is the running time of this code O(nlogn)? -

this exercise course algorithms, part 1 on coursera. said answer o(n log n). not why:

int sum = 0; (int = 1; <= n; = i*2)     (int j = 1; j <= n; j = j*2)         (int k = 1; k <= j; k++)             sum++; 

could please tell me how many times inner loop running , why answer o(n log n)?

your appreciated.

thank you.

the outer loop runs log(n) times. both inner loops run combined sum_{x=1}^{log(n)} 2^x times, each summand represents 1 iteration of middle loop. using geometric sum formula makes in total log(n)(1-2^(log(n)+1))/(1-2) = log(n)(2n-1) iterations, o(n*logn)