Solved

# RunTime Complexity

Posted on 2007-04-09
1,343 Views
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
0
Question by:nikorba
• 7
• 6
• 4
• +2

LVL 84

Assisted Solution

ozo earned 60 total points
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

LVL 84

Expert Comment

> if ((j % Math.Sqrt(n))==0)
How many times would this be true?
0

LVL 84

Expert Comment

> Prod = 2k * 2k-1 * 2k-2 * 2k-3 * 2k-4 *2k-5 *………* 21  = 2k  -  2
Are you saying Prod is less than 2k?
0

LVL 12

Expert Comment

Sorry, not an answer, just a point

log2(2k) = 1+log2(k)  {not k; log2(2^k)=k}
0

LVL 2

Author Comment

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

LVL 53

Accepted Solution

Infinity08 earned 65 total points
>> 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

LVL 2

Author Comment

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

LVL 53

Expert Comment

>> I think the 1st two functions are correct

No, see my previous post ...
0

LVL 2

Author Comment

>>>No, see my previous post ...

I saw it,,,
try to solve it numerically
try a number with the F1
0

LVL 53

Expert Comment

>> 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

LVL 84

Expert Comment

0

LVL 53

Expert Comment

I agree ... nikorba apparently didn't believe us when we pointed out his mistakes ...
0

LVL 2

Author Comment

I still think that my answers were right ,,, that;s it
0

LVL 53

Expert Comment

Then I wonder why you were asking our help, if you can't accept what we have to say ?
0

LVL 2

Author Comment

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

LVL 53

Expert Comment

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

LVL 20

Expert Comment

OK - this is one of these "why the hell I recommended delete" :)

So what we do with the question?
0

LVL 53

Expert Comment

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

LVL 2

Author Comment

I'm sorry I discovered that I was wrong
sorry everyone :)
0

## Featured Post

One of Google's most recent algorithm changes affecting local searches is entitled "The Pigeon Update." This update has dramatically enhanced search inquires for the keyword "Yelp." Google searches with the word "Yelp" included will now yield Yelp a…
Iteration: Iteration is repetition of a process. A student who goes to school repeats the process of going to school everyday until graduation. We go to grocery store at least once or twice a month to buy products. We repeat this process every mont…
In this tutorial you'll learn about bandwidth monitoring with flows and packet sniffing with our network monitoring solution PRTG Network Monitor (https://www.paessler.com/prtg). If you're interested in additional methods for monitoring bandwidt…
This video demonstrates how to create an example email signature rule for a department in a company using CodeTwo Exchange Rules. The signature will be inserted beneath users' latest emails in conversations and will be displayed in users' Sent Items…