RunTime Complexity
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
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
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
> Prod = 2k * 2k-1 * 2k-2 * 2k-3 * 2k-4 *2k-5 *………* 21 = 2k - 2
Are you saying Prod is less than 2k?
Are you saying Prod is less than 2k?
Sorry, not an answer, just a point
log2(2k) = 1+log2(k) {not k; log2(2^k)=k}
log2(2k) = 1+log2(k) {not k; log2(2^k)=k}
ASKER
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
Thanks
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
Thanks
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
OZo didn't saw my 2nd comment :)
I think the 1st two functions are correct
I think the 1st two functions are correct
>> I think the 1st two functions are correct
No, see my previous post ...
No, see my previous post ...
ASKER
>>>No, see my previous post ...
I saw it,,,
try to solve it numerically
try a number with the F1
I saw it,,,
try to solve it numerically
try a number with the F1
>> try to solve it numerically
>> try a number with the F1
What do you mean ?
You said :
Prod = 2^k * 2^(k-1) * 2^(k-2) * 2^(k-3 )* 2^(k-4) *2^(k-5 )*………* 2^1 = 2^(k) - 2
And that's simply not true ... (see my earlier post)
>> try a number with the F1
What do you mean ?
You said :
Prod = 2^k * 2^(k-1) * 2^(k-2) * 2^(k-3 )* 2^(k-4) *2^(k-5 )*………* 2^1 = 2^(k) - 2
And that's simply not true ... (see my earlier post)
there were answers
I agree ... nikorba apparently didn't believe us when we pointed out his mistakes ...
ASKER
I still think that my answers were right ,,, that;s it
Then I wonder why you were asking our help, if you can't accept what we have to say ?
ASKER
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
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
If your teacher says that this :
Prod = 2^k * 2^(k-1) * 2^(k-2) * 2^(k-3 )* 2^(k-4) *2^(k-5 )*………* 2^1 = 2^(k) - 2
is correct, then he's wrong :)
2^(k) - 2 is smaller than 2^(k), while Prod is a lot larger. How can those two be equal ?
Try filling in k=3 for example. You say that :
Prod = 2^3 * 2^(2) * 2^(1) = 2^(3) - 2
Prod = 2^6 = 2^3 - 2
Prod = 64 = 6
How can 64 be equal to 6 ???
Prod = 2^k * 2^(k-1) * 2^(k-2) * 2^(k-3 )* 2^(k-4) *2^(k-5 )*………* 2^1 = 2^(k) - 2
is correct, then he's wrong :)
2^(k) - 2 is smaller than 2^(k), while Prod is a lot larger. How can those two be equal ?
Try filling in k=3 for example. You say that :
Prod = 2^3 * 2^(2) * 2^(1) = 2^(3) - 2
Prod = 2^6 = 2^3 - 2
Prod = 64 = 6
How can 64 be equal to 6 ???
OK - this is one of these "why the hell I recommended delete" :)
So what we do with the question?
So what we do with the question?
If nikorba still wants our help, then I'll be glad to provide that ... if not, then this question can be PAQ'd for ozo as he was first :)
ASKER
I'm sorry I discovered that I was wrong
sorry everyone :)
sorry everyone :)
How many times would this be true?