# RunTime Complexity

Hi there Buddies.
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
LVL 2
###### Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Commented:
I gather that 2k means 2^k or 2**k

> Second Function :
> Complexity as a function of n  is n*log(n)
I don't think that's right
0
Commented:
> if ((j % Math.Sqrt(n))==0)
How many times would this be true?
0
Commented:
> Prod = 2k * 2k-1 * 2k-2 * 2k-3 * 2k-4 *2k-5 *………* 21  = 2k  -  2
Are you saying Prod is less than 2k?
0
CTO & OpenERP Project managerCommented:
Sorry, not an answer, just a point

log2(2k) = 1+log2(k)  {not k; log2(2^k)=k}
0
Author Commented:
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
0
Commented:
>> Prod = 2^k * 2^(k-1) * 2^(k-2) * 2^(k-3 )* 2^(k-4) *2^(k-5 )*………* 2^1  = 2^(k)  -  2

Not really (as ozo already noted).

2^(k(k + 1)/2)

is more like it ... can you explain why ?

>> Complexity as a function of n  is n*log(n)

That's not correct ... you have nested loops of the same type as in the first function ... what does that give complexity wise ?
0

Experts Exchange Solution brought to you by

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Author Commented:
OZo didn't saw my 2nd comment :)
I think the 1st two functions are correct
0
Commented:
>> I think the 1st two functions are correct

No, see my previous post ...
0
Author Commented:
>>>No, see my previous post ...

I saw it,,,
try to solve it numerically
try a number with the F1
0
Commented:
>> 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)
0
Commented:
0
Commented:
I agree ... nikorba apparently didn't believe us when we pointed out his mistakes ...
0
Author Commented:
I still think that my answers were right ,,, that;s it
0
Commented:
Then I wonder why you were asking our help, if you can't accept what we have to say ?
0
Author Commented:
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
0
Commented:
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 ???
0
Commented:
OK - this is one of these "why the hell I recommended delete" :)

So what we do with the question?
0
Commented:
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 :)
0
Author Commented:
I'm sorry I discovered that I was wrong
sorry everyone :)
0
###### It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Algorithms

From novice to tech pro — start learning today.