Develop three functions that must satisfy the Big-O requirements shown here: (1)
ID: 3546246 • Letter: D
Question
Develop three functions that must satisfy the Big-O requirements shown here:
(1) Develop a function that uses a loop to calculate x^n in O(n)
(2) Develop a function that recursively calculates x^n in O(n)
(3) Develop a function that recursively calculates n^n in O(logn)
Use the following numbers to test each function:
a) x=2, n=10
b) x=2, n=30
c) x=2, n=50
(4) Develop a function that has O(2^n) time complexity. Try the following numbers as input:
n= 1,5,10,15,20,25,30.....until the execution is too long to wait
submit the time of the last execution, usually in the range of >= 30 minutes
You can have One program that consists of 4 functions described above.
Explanation / Answer
#include<iostream>
using namespace std;
/* Function to calculate x raised to the power n in O(n) using Loop*/
long int powI(int x, unsigned int n)
{
long int temp = 1;
for(int i=1; i<=n ;i++) {
temp=temp*x;
}
return temp;
}
/* Function to calculate x raised to the power n in O(n) using recursion*/
long int powII(int x, unsigned int n)
{
if( n == 0)
return 1;
else if (n%2 == 0)
return powII(x, n/2)*powII(x, n/2);
else
return x*powII(x, n/2)*powII(x, n/2);
}
/* Function to calculate x raised to the power n in O(logn)*/
long int powIII(long int x, unsigned int n)
{
long int temp;
if( n == 0)
return 1;
temp = powIII(x, n/2);
if (n%2 == 0)
return temp*temp;
else
return x*temp*temp;
}
/* recursive Fibonacci number calculation is O(2^n). */
unsigned long int Fib(unsigned int n)
{
if (n <= 1)
return n;
else
return Fib(n - 1) + Fib(n - 2);
}
int main() {
int x =2 , n1=10 , n2 = 30 , n3 =50;
cout<<"using loop function in o(n) time ";
cout<<powI(x , n1)<<endl;
cout<<powI(x, n2)<<endl;
cout<<powI(x,n3)<<endl;
cout<<"using recursive function in o(n) time ";
cout<<powII(x , n1)<<endl;
cout<<powII(x, n2)<<endl;
cout<<powII(x,n3)<<endl;
cout<<"using recursive function in o(logn) time ";
cout<<powIII(x , n1)<<endl;
cout<<powIII(x, n2)<<endl;
cout<<powIII(x,n3)<<endl;
cout<<"recursive Fibonacci number calculation is O(2^n). ";
int i =0;
int j =1;
do {
cout<<"n = "<<j<<" result = "<<Fib(j)<<endl;
i=i+1;
j=5*i;
}while(j<200);
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.