Time Complexity of Triple Nest Loop?

Question

for(i=0; i<n; i++)
{
    a[i]=0;
    for(i=0; i<n; i++)
    {
        for(j=0; j<n; j++)
        {
            a=3;
        }
    }
}

This is a triple nested loop. My book states that the running time is: O(N) + O(N^2) = O(N^2)

Shouldn't it be O(N^3)? All 3 loops depend on each other. It will run for N*N*N times.

Answer 1

It is because the loop #1 and loop #2 are using the same count variable, i during comparison.

At the end of the 2nd loop using i, the value of i is n which makes it break out of the outer loop as well. One loop is completely redundant there.

---

#include <stdio.h>
int main(){
    int x = 0;
    int n = 20;
    int i, j;
    for(i=0; i<n; i++) //this loop runs once
    {
        for(i=0; i<n; i++) //this loop runs n times
        {
            for(j=0; j<n; j++) //this loop also runs n times
            {
                x++;
            }
        }
    }
    printf("%d", x);
}

It is in O(N^2) time that the whole is running.

Example

Answer 2

I don't think that they is an error in your book. You have to look at your code more deeply: The two first loops use the same variable for the loop, so what will happen is the following:

after ther first bracket, i is equal to 0 and you go to the second loop. When the second loop ends the first one will end to because both loops use the condition i

Actually I don't see where the O(N) comes from but the global complexity should be of O(N^2)

Answer 3

This isn't n^3 since the variable i is reused in the inner loop, making it n^2. Not sure where the book gets the O(n) in that though.