Problem Detail: 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
Asked By : TacoB0t
Answered By : Anton Trunov
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)$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/52939
