Find time complexity (Big O) and (Omega)

Question

 for i:=1 to n do

        j:=2;
        while j<i do
              j:=j^4;
        end
 end

I looks like while loop will have $\dfrac{log\ (i)}{4 \cdot log\ (j)}$ iterations

Answer 1

Usually, when talking about time complexity we talk about the time complexity relative to an input. In this case, it would appear that $n$ is our input.

We can begin by analyzing each iteration of the outer loop. For each $i$, we enter a while loop where the number 2 gets exponentiated to the 4th power until it is greater than $i$. Note that $(x^a)^b=x^{ab}$ so if we let $m$ be the number of iterations required to meet this condition, we have approximately $2^{4m}=i$ or

$$m=\frac{1}{4}\log_2i$$

Since we are looking at Big O, we can ignore constants and this becomes the following simpler formula

$$m=\log i$$

Now we can look at the outer loop as a whole. We know it goes through $n$ iterations so the overall number of iterations is

$$\sum_{i=1}^n\log i$$

With a little work and the identity $\log a+\log b=\log ab$, you can show that this reduces to approximately $n\log n$. Thus, the time complexity of this code snippet is $O(n\log n)$.