Time complexity (in Θ –notation) in terms of n

Question

I am struggling quite a bit trying to solve these and any help would be greatly appreciated.

a)

sum =0;

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

                    sum++;

and

b)

sum = 0 ;

for ( i = n ; i ≥ 1; i = i/4 )
  for ( j = 0 ; j < n^4 ; j++ )

                sum++ ;

I am looking for the time complexity in Θ –notation in terms of n.

For the first one, I got N^5 log base 4N. But I am not sure if that's correct or not. Any explanations would surely be extremely beneficial.

Thank you!

Answer 1

You need to start from the inner loop.

As $j$ is repeatedly multiplied by a constant, if follows a geometric progression, and $j=4^m$ where $m$ is the iteration count. The iterations stop as soon as $4^m\ge n^4$, or $m=\lfloor\log_4(n^4)\rfloor$, which is in $O(\log(n))$.

For a) the outer loop induces

$$T(n)=\sum_{i=0}^{n-1}\lfloor\log_4(n^4)\rfloor,$$ which can be show to be in $O(n\log(n))$.

For b), we also have a geometric progression, of common ratio $\frac14$, so that $i=\lfloor\frac n{4^k}\rfloor$, which can be approximately written $\log_4(i)=\log_4(n)-k$. Then by summation (using the triangular numbers),

$$T(n)\approx\sum_{k=\log_4(n)}^04(\log_4(n)-k)=2\log_4(n)(\log_4(n)+1)$$

which is in $O(\log^2(n))$.