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


How would I go about finding the time complexity in big theta notation in terms of n for this code?



closed as off-topic by Antonio Vargas, JMP, Claude Leibovici, user91500, John B Jun 9 '16 at 9:23

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Antonio Vargas, Claude Leibovici, user91500, John B
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ What's n4? And the indentation of sum++; is off. Otherwise: Ask yourself how many iterations the outer for will have, and how many iterationns the inner sum (j) will have. Then multiply them together. $\endgroup$ – Maximilian Gerhardt Jun 8 '16 at 20:32
  • $\begingroup$ Max, I realized I forgot to include the ^ when typing n^4, my apologies. But thanks for your help, I think I can figure it out based off that. $\endgroup$ – drpatrickbateman Jun 8 '16 at 20:53

Spoiler solution:

The outer for loop for(i=0; i < n; i++) will have exactly $n$ iterations ($i=0,\;..\;,n-1$).

The inner for loop for(j=1; j < n^4; j *= 4) is trickier. It starts at $j=1$ and goes at maximum to $n^4$, but the value of $j$ is quadrupled in each iteration. That means that $j$ actually grows as $4^x$ (exponentially). That is, $j=1,4,16,64,256,1024,4096,16384,65536..$ For $l = n^4$ as a constant upper bound, the function $4^x$ reaches that value for $x = \log_4(l) = \log_4(n^4)$. That is, the number of iterations in the inner loop is $$\left \lceil \log_4(n^4) \right\rceil = \left \lceil 4\log_4(n) \right\rceil$$ (Recheck this by plugging in $n=2$, $n=4$, $n=16$, computing the upper bound of the for loop and checking at which iteration $j$ will be greater than or equal to the bound)

Multiplying them together, we have the total complexity as

$$\mathcal{O}(n\cdot 4\log_4(n)) = \mathcal{O}(n\log n).$$ (base of the logarithm doesn't matter as well as multiplicative constants)


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