CODEWITHSUNDEEP
javaalgorithm
slim shady
slim shady

Reputation: 3

What will be the time complexity of a for loop nested 2 times?

So the algorithm for which the time complexity is to estimated is this

int a = 0;
for (i = 0; i < n; i++)   //runs from i-n;
    for (j = i; j < i * i; j++) // runs from i - i*i;
        for (k = 0; k < j; k++) //runs from 0 - j;
            a++;

I have commented the basic details that i have understood about the algorithm.

The outer loop clearly runs O(n) times and first inner loop runs from 'i' to 'i*i'

The second inner loop runs '0' to 'j'

I also know i have to apply the rule of products.

But I am unable to calculate the time complexity of the two inner loops relative to 'n'.

Please correct me if I'm wrong with my explanation.

Upvotes: 0

Views: 137

Answers (2)

Deepak Tatyaji Ahire
Deepak Tatyaji Ahire

Reputation: 5321

Whenever there is a doubt always use mathematics as the mathematical proofs are more palatable like strong intuitions.

Let n = size of input.

The innermost loop or lets call it as the 3rd loop runs for j+1 number of times.

The inner loop or 2nd loop runs for i*i - i number of times.

Finally, the outer loop for n times.

So, the number of iterations for the entire program can be expressed in mathematical terms as shown in the following figure:

enter image description here

Upvotes: 1

KuzminK13
KuzminK13

Reputation: 336

When you have multiple levels of for loops, analyze the complexity of each loop in isolation and then multiply them together.

In this example, the complexity of the first loop is O(n), like you said.

The complexity of the second loop is O(n^2) because in the worst case, the number of operations you have to perform is on the order of i*i which could be as big as n^2. It doesn't matter that it doesn't start at zero either because in an expression like O(n^2 - n), everything but the highest order term gets ignored.

The third loop also takes O(n^2) because in the worst case, you could have as many as j operations would again could be as big as n^2.

Lastly a++ happens in constant time. Multiply everything together and you have a complexity of O(n^5).

Upvotes: 0

Related Questions