Question

What is the complexity of the given code as a function of the problem size n?  Show all of the details of your analysis.

for (int i = 0; i < 2*n; i++)

{

   if (i == n)

   {

      for (int j = 0; j < i; j++)

         for (int k = 0; k < i; k++)

            O(1)

   }

   else

   {

      for (int j = 0; j < i; j++)

         O(1)

   }

}

Answer 1

for (int i = 0; i < 2*n; i++)
{
if (i == n)
{
for (int j = 0; j < i; j++)
  for (int k = 0; k < i; k++)
  O(1)
}
else
{
   for (int j = 0; j < i; j++)
  O(1)
   }
}

Analysis :
When i < n :
else condition will work which has a loop that goes i times and a constant operation inside that.
Thus , for i = 0-n-1,
Number of opeartions = 0,1,2,3,.....n-1
Total opeartion = n*(n-1)/2 equivalent to O(n^2)

when i == n :
This condition will come only 1 time
There are two for loops that goes n times each because i==n
Thus , total operation = n*n equivalent to O(n^2)

when i > n :
else condition will work which has a loop that goes i times and a constant operation inside that.
Thus , for i = n+1 to 2*n-1,
Number of opeartions = (n+1),(n+2)......(2*n-1)
Total opeartion = (n-1)(n+1 + 2*n -1)/2 [ ap sum = n/2(first term + last term) ]
=(n-1)(3n)/2 equivalent to O(n^2)

Thus ,
The overall complexity = O(n^2 + n^2 + n^2) = O(3n^2) which is equivalent to O(n^2)