CODEWITHSUNDEEP
algorithmcomplexity-theory
USER_NAME
USER_NAME

Reputation: 1037

What will be the complexity of for loop if nothing is happening in the body of loop

Code:

            int c = 0;
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    c = i * j;
                }
            }

Time Complexity: O(n2)

Now what will be the complexity of following code:

            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    //c = i * j;
                    // nothing is happening inside the loop
                }
            }

whether complexity will be same as above( O(n2) ) or something else??

Upvotes: 3

Views: 215

Answers (2)

Анатолий
Анатолий

Reputation: 2857

For both complexity is O(N^2).

Upvotes: 1

amit
amit

Reputation: 178491

Theoretically - yes because there is still the issue of increasing the i and j which still needs to happen, and comparing them to the end value in each iteration.

However - compilers might optimize it to be done in constant time, and just set the post values of i and j.

Upvotes: 7

Related Questions