Finding the Time Complexity in Big theta notation

Question

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

                   sum++;

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

Thanks!

Answer 1

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)