# Time complexity of algorithm with three loops and if statement

Suppose I have this c++ code:

for(int i=0; i<n*n*n; i++) {
for(int j=0; j<n*n; j++) {
if(i>n && j<n) {
for(int k=0; k<n*n*n*n; k++) s++;
}
}
}


I need to find its time complexity.

What I tried doing is: I tried determining the times the if clause would be fulfilled, and multiplying that with $$n^4$$.

However, I have a hard time determining how many times the if clause will be fulfilled. The values of i go from $$n+1$$ to $$n^3-1$$, while the values for j go from $$0$$ to $$n-1$$.

Now, for each value of i for which the first part of the condition is true, I have that there are $$n$$ values of j for it.

Unfortunately, this is as far as I have come. Could anyone help me out further?

1. The if is executed when $$n and $$0\leq j . This means that the values of $$i$$ which satisfy the condition are $$n^3-n-1$$, while the values of $$j$$ which satisfy the condition are $$n-1$$. For each value of $$i$$ for which the condition on it is satisfied you can choose every values of $$j$$ which satisfies the condition of it and viceversa. It means that the if is executed $$(n^3-n-1)(n-1) = \Theta(n^4)$$ times. In these cases the inner-most loop is executed $$n^4$$ times and each execution has a constant cost. So, the total cost of this case is $$\Theta(n^4\cdot n^4)=\Theta(n^8)$$.
2. In the remaining cases, i.e. $$\approx n^5-n^4=\Theta(n^5)$$ times, the if is not executed and the cost of one iteration the two outer-most loops is constant (just a check on the if condition), thus the cost of this case is $$\Theta(n^5)$$.
Summing up, the total cost is: $$\Theta(n^8)+\Theta(n^5)= \Theta(n^8) \ .$$
PS: If you are not familiar with asymptotic notation, look at it (big-O, Theta, Omega, small-o notations or Landau symbols). You can consider $$\Theta(n^i)$$ as $$\approx n^i$$ while reading this answer. Then I suggest you to go check these topics.