Little bit confusing to compute time complexity of nested loop [duplicate]

Question

This question already has an answer here:

• Is there a system behind the magic of algorithm analysis? 3 answers

1 for(i=1; i<=n; i++){
2    for(j=1; j<=n; j*=2){
3      a[i][j]=b[i][j-1]+1;
4    }
5 }

line 1 : n+1 times

lnie 2 : n/2+1 times

line 3 : constant time c

so, I computed $(n+1)(n/2+1)c=(n^2+2n+2)/2+c=\theta(n^2)$

Is it right computation?

Answer 1

Line $2$ is executed for $j=1,2,4,\cdots 2^k$ where $k$ is such that $2^k\le n<2^{k+1}$. Hence, taking the logarithm

$$k\le\log_2n<k+1$$or

$$k=\lfloor\log_2n\rfloor.$$

So the total time is

$$n\lfloor\log_2n\rfloor c=\Theta(n\log n).$$