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?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community1 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?
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).$$
j*=2
rather thanj+=2
. $\endgroup$ – Yuval Filmus Apr 15 '18 at 9:31