-1
$\begingroup$

This question already has an answer here:

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?

$\endgroup$

marked as duplicate by David Richerby, Discrete lizard, Community Apr 15 '18 at 10:36

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.

  • $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Apr 15 '18 at 8:24
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – Raphael Apr 15 '18 at 8:24
  • $\begingroup$ Please note our reference question that explains in detail how to analyse algorithms like this rigorously. $\endgroup$ – Raphael Apr 15 '18 at 8:24
  • $\begingroup$ On line 2, you have j*=2 rather than j+=2. $\endgroup$ – Yuval Filmus Apr 15 '18 at 9:31
1
$\begingroup$

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).$$

$\endgroup$

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