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