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
Hi there ,,, well , there are some mistakes in the Question ,,, because I copied it from the word Document ,,, so I thought that the exponent will appear correctly ...I will fix it now
Here is the Question
1. Let n=2^k , 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(2^k) = k ,,, so It’s O(k)
Prod = 2^k * 2^(k-1) * 2^(k-2) * 2^(k-3 )* 2^(k-4) *2^(k-5 )*………* 2^1 = 2^(k) - 2
Second Function :
Complexity as a function of n is n*log(n)
Complexity as a function of k is 2^k*log(2^k) = (2^k )* k ,,, so It’s O(2^k)
Prod = 2^k * 2^(k-1) * 2^(k-2) * 2^(k-3 )* 2^(k-4) *2^(k-5 )*………* 2^1 = 2^(k) - 2
I appreciate ur help ,,, at first I wasnt sure about my answers so I asked u
but after a while the I asked the lecturer and he said my answers were right
I really thank u so much for ur help but that what happened
> Second Function :
> Complexity as a function of n is n*log(n)
I don't think that's right