Run Time Analysis Provide the tightest big-Oh bound on the run time for each of the following methods. void padawan(int n) { if( n <= 1 ) time++; else { for(int i=0; i
- Run Time Analysis
Provide the tightest big-Oh bound on the run time for each of the following methods.
void padawan(int n)
{
if( n <= 1 )
time++;
else
{
for(int i=0; i<n; i++)
time++;
padawan(n/3);
padawan(n/3);
padawan(n/3);
}
}
void nerfHerder(int n)
{
if( n <= 1 )
time++;
else
{
for(int i=0; i<n; i++)
time++;
nerfHerder(n-1);
}
}
void squire(int n)
{
if( n <= 1 )
time++;
else
{
squire(n/2);
squire(n/2);
for(int i=0; i<n; i++)
for(int j=i; j<n; j++)
time++;
squire(n/2);
squire(n/2);
squire(n/2);
squire(n/2);
squire(n/2);
squire(n/2);
}
}
void jedi(int n)
{
if( n <= 147 )
time += 54;
else
{
for(int i=0; i<n/2; i++)
time++;
jedi(n/3);
for(int i=0; i<13*n; i++)
time++;
jedi((2*n)/3);
}
}
void strass(int n)
{
if( n<=1 )
time++;
else
{
strass(n/2);
strass(n/2);
strass(n/2);
for(int i=0; i<n; i++)
for(int j=i; j<n; j++)
time++;
strass(n/2);
for(int i=n/2; i<n; i++);
time ++;
strass(n/2);
strass(n/2);
strass(n/2);
}
}
void sithLord(int n)
{
if( n <= 200 )
time += 700;
else
{
sithLord((7*n)/10);
for(int i=0; i<n; i++)
time++;
sithLord(n/5);
for(int i=0; i<130*n; i+=10)
time++;
}
}
void hanoi(int n)
{
if( n==1 )
time++;
else
{
hanoi(n-1);
time++;
hanoi(n-1);
}
}
int fib(int n)
{
if( n==0 )
return 0;
else if( n==1 )
return 1;
else
{
return fib(n-1) + fib(n-2);
}
}
int pow(double x, int n)
{
if( n==0 )
return 1;
else
{
double halfpower = pow(x,n/2);
if( n % 2 == 0 )
{
return halfpower*halfpower;
}
else
{
return halfpower*halfpower*x;
}
}
}
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 1 images
