Solved
RunTime Complexity
Posted on 2007-04-09
Hi there Buddies.
I've already answered the first 2 Functions But I wanna know if my answers are true
But I couldnt find a solution for the 3rd function
Here is the Question
1. Let n=2k , Determine RunTime Complexity for each of the following 3 functions as a function of k.
2. Calculate prod as function of k in each case.
static int F1(int n)
{
int prod=1;
while (n>1)
{
prod = prod *n;
n=n/2;
}
return prod;
}
static int F2(int n)
{
int prod=1; int m;
while (n>1)
{
m=n;
while (m>1)
{
prod = prod *2;
m=m/2;
}
n=n/2;
}
return prod;
}
static double F3(int n)
{
double prod=1; int x=0;
for (int i=1; i<=n; i++)
for (int j=1; j<=n*n; j++)
if ((j % Math.Sqrt(n))==0)
for (int m=1; m<=j; m++)
prod=prod *2;
return prod;
}
My answers for the first 2 Functions
First Function :
Complexity as a function of n is log2(n)
Complexity as a function of k is log2(2k) = k ,,, so It’s O(k)
Prod = 2k * 2k-1 * 2k-2 * 2k-3 * 2k-4 *2k-5 *………* 21 = 2k - 2
Second Function :
Complexity as a function of n is n*log(n)
Complexity as a function of 2k is 2k*log(2k) = 2k * k ,,, so It’s O(2k)
Prod = 2k * 2k-1 * 2k-2 * 2k-3 * 2k-4 *2k-5 *………* 21 = 2k - 2
Thanks