1
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

Let's divide it in two parts: when the code enters the if and when it does not.

  1. The if is executed when $n<i<n^3$ and $0\leq j <n$. 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.

$\endgroup$
1
  • $\begingroup$ Thank you for the answer. Unfortunately I have gotten it wrong, here's what I did: If i=n+1, then there are j=0,j=1...j=n-1 values for which the condition is satisfied. Then, if i=n+2 the same applies. What I did was find the sum of all natural numbers from n+1 to n^3 and multiplied that with n-1 and I got a polynomial of the seventh power. I did this because I thought that since there are n+1 values for each value of "i". $\endgroup$
    – john doe
    Nov 22, 2023 at 17:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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