Question

c++

What is the worst-case complexity of the following code fragment:

for(i = 0; i < N; i++)
{
     for(j = 0; j < N; j++)
     {
          sequence of constant time statements
     }
}

for(i = N; i > 0; i--)
{
     sequence of constant time statements
}

Answer 1

// Number of values for i is N
for(i = 0; i < N; i++)
{
     // Number of values for j is N
     for(j = 0; j < N; j++)
     {
          sequence of constant time statements
     }
}

As above two loops are nested
Time complexity 
= O(Product of number of values for loop variable)
= O(N^2)


// Number of values for i is N
for(i = N; i > 0; i--)
{
     sequence of constant time statements
}

This loop is parallel to above nested loop.
We need to add N to above time complexity

So, Total time complexity of above code is
= O() + O(N)

= O()