3 Nested for loops where third loop is dependent on first time complexity

hehe

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
        }
    }
}
wohlstad

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 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 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).

Collected from the Internet

Please contact [email protected] to delete if infringement.

edited at
0

Comments

0 comments
Login to comment

Related