Determine the BigO complexity of the following algorithm Big

Determine the Big-O complexity of the following algorithm                                Big-O: ____________________

for ( i = 0; i < n; i++ )

     Console.Write(“-“);

for ( j = 0; j < n; j++ )

     Console.Write(“*”);

Determine the Big-O complexity of the following algorithm                                Big-O: ____________________

sum = 0;

for ( i = 0; i < n; i++ )

     for ( j = 0; j < n; j++ )

           sum++;

Determine the Big-O complexity of the following algorithm                                Big-O: ____________________

factorial = 1;

for ( i = 0; i < n; i++ )

     factorial *= n;

Determine the Big-O complexity of the following algorithm                 Big-O: ____________________

for ( i = 0; i < n; i++ )

     if (n > 0)

          n -= 2;

Determine the Big-O complexity of the following algorithm                 Big-O: ____________________

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

{

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

   {

        Console.WriteLine(“i: “ + i + “ j: “ + j + “ n: “ + n);

    }

}

Design and write your own n³ algorithm

Solution

Determine the Big-O complexity of the following algorithm                                Big-O: ____________________

for ( i = 0; i < n; i++ )

     Console.Write(“-“);

for ( j = 0; j < n; j++ )

     Console.Write(“*”);

Outer loop runs n times

Inner loop runs max of n*n times

Therefore complexity is O(n*n)

Determine the Big-O complexity of the following algorithm                                Big-O: ____________________

sum = 0;

for ( i = 0; i < n; i++ )

     for ( j = 0; j < n; j++ )

           sum++;

sum=0 - 1time

i=0 -1time

i<n - n times

i++ - n times

j=0 - n times

j<n max n*n times

j++ n*n times

sum++ n*n times

Total = 3n^2+3n+2= O(n^2)

Determine the Big-O complexity of the following algorithm                                Big-O: ____________________

factorial = 1;

for ( i = 0; i < n; i++ )

     factorial *= n;

factorial =1 - 1time

i=0 - 1time

i<n - ntimes

i++ - n times

factorial =factorual *n - n times

Total =3n+2= O(n)

Determine the Big-O complexity of the following algorithm                 Big-O: ____________________

for ( i = 0; i < n; i++ )

     if (n > 0)

          n -= 2;

i=0 1 time

i<n - n times

i++ - n times

n>0 - n times

Total = 3n + 1= O(n)

Determine the Big-O complexity of the following algorithm                 Big-O: ____________________

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

{

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

   {

        Console.WriteLine(“i: “ + i + “ j: “ + j + “ n: “ + n);

    }

}

Outer loop runs n times

Inner loop runs for max 2n times

Total = 2*2n + n + n + n +1= 4n +3n+1=7n+1=O(n)

N cube algorithm :

sum = 0;

for ( i = 0; i < n; i++ )

     for ( j = 0; j < n; j++ )

for(k=0;k<n;k++)

           sum++;