Question

What are Big-O expressions for the following runtine functions?

     a) T(n)= nlog n + n log (n² )  

     b) T(n)= (nnn)²     

     c) T(n)= n^1/3 + n^1/4 + log n

     d) T(n)= 2³ⁿ + 3²ⁿ

     e) T(n)= n! + 2ⁿ

Write algorithm and program : Find the sum of the integers from 1 through n.

    a)Use iterative algorithm and program

        b) Use recursive algorithm and program.

1. Order the following functions by growth rate:
   1. 3ⁿ
   2. n
   3. n²
   4. 5
   5. n^1.3
   6. n log n²
   7. 2ⁿ
   8. 2^n/2
   9. n²log n
   10. n³

Answer 1

Solution1.:-

T(n) = nlog n + n log (n2 )	T(n) = nlog n + n log (n2 )   = nlogn + 2n log n = 3nlog n = O(nlog n)
T(n)= (nnn)2	T(n) = (nnn)2 = (n3)2 = n6 = O(n6)
T(n)= n1/3 + n1/4 + log n	T(n) = O(n1/3)
T(n)= 23n + 32n	T(n) = O(32n)
T(n)= n! + 2n	T(n) = nn + 2n = O(nn)

Solution 2. :

Iterative Algorithm: 1. Take variable sum = 0

2. For each number from 1 to n add each number to variable sum

3. return sum

Iterative Program:

#include <iostream>

using namespace std;
int main() {
  int sum= 0,n;
  cout<<"Enter value of 'n':"<<endl;
  cin>>n;
  for(int i=1;i<=n;i++)
    sum+=i;
  cout<<"Sum: "<<sum<<endl;
}

  Recursive Algorithm:

1. if n = 1, return 1. Else go to step 2

2. add 'n' to the result returned by recursion on n = n-1

  Recursive Program:

#include <iostream>

using namespace std;
int recurSum(int n) 
{ 
    if (n <= 1) 
        return n; 
    return n + recurSum(n - 1); 
}    
int main() {
  int sum= 0,n;
  cout<<"Enter value of 'n':"<<endl;
  cin>>n;
  cout<<"Sum: "<<recurSum(n)<<endl;
}

Solution 3:-

5 < n < nlog n²< n^1.3 < n² < n² log n < n³ < 2^n/2 < 2ⁿ < 3ⁿ