CODEWITHSUNDEEP
algorithmcomplexity-theorybig-oasymptotic-complexity
user2110714
user2110714

Reputation:

Computational complexity of for loops-Contradicting with myself

I have a contradiction by analyzing the running time of a program. For example, consider the following piece of code:

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

Here, the computational complexity of 1st for loop is O(n2), and for the second loop it is O(n). However, the second loop is executed n2 times whereas first loop is executed n times. For example, if we put a cout statement inside the inner loop, it outputs n2 times, but if we put a cout somewhere inside the 1st loop but outside the inner loop, it outputs n times. So why do we say the complexity of inner loop is O(n), but for outer loop it is O(n2). We say the complexity of outer loop is O(n2) but it executes n times, why is this the case? Am i doing something wrong? Thanks.

Upvotes: 0

Views: 1238

Answers (3)

Husnain Iqbal
Husnain Iqbal

Reputation: 466

Let say, n = 7 ; then 

for(int i=0 ; i< 7 ; i++) //time complexity is : (1) + (7+1) + (7)
{
    for(int j=0;j<7;j++) //  time complexity is: (1) + [(7+1)+(7+1)+(7+1)+(7+1)+(7+1)+(7+1)+(7+1)] + (7)
    {
         .....
    }
}

Total time complexity = [2+2(7)] + [1 + (7+1)^2 + 7]

Now replace 7 = n ; We will get

Total time complexity = [2+2n] + [1 + (n+1)^2 + n] = 2 + 2n + 1 + (n^2 + 2n + 1) + n = n^2 + 5n + 4

Here the dominant term is n^2. So the worst case will be O(n^2)

Upvotes: 0

Vallabh Patade
Vallabh Patade

Reputation: 5110

Outer loop will run for n times and inner loop will run for n times for every iteranion of outer loop making inner loop to run for n^2 times. Thus statements in inner loop will get executed for n^2 times.

Upvotes: 1

John K&#228;ll&#233;n
John K&#228;ll&#233;n

Reputation: 7943

The inner loop executes n times, which takes O(n). The outer loop executes the inner loop n times, but you have to account for the cost of the inner loop for each of those n outer loop executions. This makes it O(n * O(n)) = O(n^2).

Upvotes: 1

Related Questions