Consider the following algorithm, where $n$ is a parameter.

sum = 0 ;
   for ( i = 0 ; i < n ; i++ )
      for ( j = 1 ; j <  n^3 ; j = 3*j )
         sum++ ;

What is the time complexity (in $\Theta$-notation) in terms of n?

So far, this is what I've done: The running time is $\Theta (N^4)$ Because the for loop’s condition is depend on $n$ and is incremented by $1$, and then inside running time is $O(1)$. I feel i'm wrong here. Any help would be appreciated.

  • $\begingroup$ I edited your post and assumed that 'n3' should have been 'n^3'. Feel free to correct it if it means something else. $\endgroup$ – punctured dusk Jun 6 '14 at 18:29
  • $\begingroup$ Voted to reopen--showing your work is good. :) Regarding your answer--you're close, but the inner for loop does not increment j by $1$ each iteration. $\endgroup$ – apnorton Jun 7 '14 at 2:17

The inner loop runs in $\Theta(\log_3(n^3))$ because we can multiple $j=1$ by $3$, $\log_3(n^3)$ times before $j$ is greater than $n^3$. The outer loop executes exactly $n$ times. So we get $\Theta(n\log_3(n^3))$ which we can simplify to $\Theta(n\cdot 3\cdot\log(n))= \Theta(n\log(n))$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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