2
$\begingroup$

This question already has an answer here:

I'm confused about the complexity of the following code:

for(i=1; i<=n; i = 2*i)
     for(j=1; j<=i; j++)
        print A[j]

I know that the first loop is logn, but I'm confused on what the second for loop would be since j is bound to i. Is this simply O(logn)?

I've plotted out the output as follows and thought it would be O(nlogn):

Assuming n = 8 or higher

i=1  j=1
i=2  j=1,2
i=4  j-1,2,3,4
i=8  j=1,2,3,4,5,6,7,8
$\endgroup$

marked as duplicate by David Richerby, Luke Mathieson, vonbrand, Juho, Kaveh Feb 20 '16 at 2:09

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

9
$\begingroup$

The number of iterations for the outer loop is $\lfloor \log n \rfloor$. The number of iterations for the inner loop is $i = 2^k$, where $k$ is the number of current iteration of the outer loop. So the number of computational steps is proportional to $$\sum_{k = 0}^{\lfloor \log n \rfloor}{2^k} = 2^{\lfloor \log n \rfloor + 1} - 1.$$ Using the following inequality $$n - 1 < 2^{\lfloor \log n \rfloor + 1} - 1 < 2n,$$ one can get that the time complexity of the algorithm is $\Theta(n)$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.