C++ (Big-O Notation)

Please, explain each code with a separate full program using these functions. (explain clearly)

O (n log n) Lineararithmic

int NlogN ( const int a[] , int n)

{

int result = 0;

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

for ( int i=n ; i > 0 ; i /= 2 )

{

result += a[i -1];

}

return result ;

}

O(n^c) Polynomial / Algebraic

Where c>2

int p( const int a[] , int n)

{

int result = 0;

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

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

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

result += a[k];

return result ;

}

O (c^n) Exponential

Where c>1

O(2n ) denotes an algorithm whose growth doubles with each additon to the input data set. int exp(int n)

{

if (n <= 1)

return n;

return exp (n - 2) + exp(n - 1) ;

}

O(n!) Factorial

A classic example is solving the traveling salesman problem using a brute-force approach.

for ( int i = 1; i <= factorial (n) ; ++i )

{

cout << "Hey - Im busy looking at: " + i) ;

}

If n is 8, this algorithm will run 8! = 40320 times!