0

I'm trying to find the time complexity for 3 nested for loops. I'm a little lost on how to do this because the the first and third are dependent. From what I did I found that the pattern is n(1 + 2 + 3) so O(n^2) but I'm unsure if that's right. I'm also unsure if this includes the j loop or would I have to multiply a n to my current answer. Any help is much appreciated.

for (int i = 0; i < n*n; i++) {
    for (int j = 0; j < n; j++) {
        for (int k = 0; k < i; k++) {
            // print some statement here
        }
    }
}
Chris
  • 26,361
  • 5
  • 21
  • 42
hehe
  • 11
  • 3

1 Answers1

1

Short Answer:

Assuming the innermost loop operation is O(1), the time compexity of your code is O(n^5).

Longer Answer:

Let's start with a simpler example of 2 dependent loops:

for (int i=0; i<n; ++i) {
    for (int j=0; j<i; ++j) {
        // Some O(1) operation
    }
}

The outer loop will run n times and the inner loop will run 1...n times, and on average:

(1 + 2 + ... + n)/n = n(n+1)/2/n = O(n)

So the overall complexity for this simpler example is O(n^2).

Now to your case:
Note that I assumed the operation in the innermost loop is done in O(1).

for (int i=0; i< n*n; i++){
   for (int j=0; j<n; j++){
       for (int k=0; k<i; k++){
          // Some O(1) operation
       }
   }
}

The 1st outer loop will run n^2 times.
The 2nd outer loop (i.e. the middle loop) will run n times.
So the 2 outer loop together will run in O(n^3).
The number of times the inner loop will run on average is now O(n^2) because the number of iterations will now be 1..n^2 (instead of 1..n):

(1 + 2 + ... n^2)/n^2 = (n^2)(n^2+1)/2/(n^2) = O(n^2).

Therefore the overall time complexity is O(n^5).

Addendum:
The code below is not in any case a proof regarding the complexity, since measuring for specific values of n does not prove anything about the asymptotic behavior of the time function, but it can give you a "feel" about the number of operations that are done.

#include <iostream>
#include <ctype.h>

void test(int n)
{
    int64_t counter = 0;
    for (int i = 0; i < n * n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < i; k++) {
                counter++;
            }
        }
    }
    std::cout << "n:" << n << ",  counter:" << counter << std::endl;
}

int main()
{
    test(10);
    test(100);
    test(1000);
}

Output:

n:10,  counter:49500
n:100,  counter:4999500000
n:1000,  counter:499999500000000

I believe it is quite clear that the number of operations is close to n^5/2, and since constants like 1/2 do not apply: O(n^5).

wohlstad
  • 12,661
  • 10
  • 26
  • 39
  • In your final observation it may be worth clarifying by noting that constants (in this case 1/2) do not apply in complexity estimates. – Chris Sep 17 '22 at 07:26
  • @Chris I thought it was obvious and therefore didn't mention it (the level of the question was not so basic). But please feel free to edit my answer and add the claraification where you think it is the most appropriate. – wohlstad Sep 17 '22 at 07:29
  • sorry but there is no way to get a time complexity of O(n^5) what do you wanted to explain about the first loop with n^2 ? i disagree with your statement "cause the number of iterations will now be 1..n^2 (instead of 1..n)" im keeping it really simple disregarding dependencies each loop runs O(1) for each item iteration. i dont see a way to go further than O(n^3) no downvote at all cause in some cases the time complexity can be lesser than n^3 – jmvcollaborator Sep 17 '22 at 07:45
  • 1
    @jmvcollaborator as you can see in the result of the test I posted, the complexity is clearly **not** O(n^3). Of course my test is not a mathematical proof (as I noted myself) but in this case it is quite clear that O(n^3) cannot be an upper bound for the number of operations required for a given `n`. You can run my code youself and see the same result. – wohlstad Sep 17 '22 at 07:57
  • i will keep this really simple...complexity can not be greater than n^3 as long as theres something weird in between than increases the number of processing items on each loop. BUT no matter what or how each loop does O(1) per item. not mean to bother you but i would appreciate a working example or concrete explanation where complexity goes beyond N^3 we are all here to learn, thanks buddy and take my comment vote. – jmvcollaborator Sep 17 '22 at 08:14
  • @jmvcollaborator The outer loop itself does **n*n == n^2** iterations (note `for (int i = 0; i < n*n; i++)` in the code). So even if the other 2 inner loops were doing n iterations each the overall complexity would be O(n^4) (O(n^2)*O(n)*O(n)). In our case the innermost loop does more - O(n^2), so overall it's O(n^5). This is what the comments to your answer are trying to tell you. – wohlstad Sep 17 '22 at 08:23
  • yes that n*n ends up as actually a number and just iterates by O(1) more times. but theres no chance to make it exponentialy, thinking about one of the border cases it can increase the complexity in terms of O(dependent value) but anyways it ends up with O(1), I'm seeing the glass half full and this is a worth thread and from my end a kind debate. – jmvcollaborator Sep 17 '22 at 08:58