Learn to build web apps and services, IoT apps, and mobile backends by covering the fundamentals of ASP.NET Core and exploring the core foundations for app libraries.

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

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with Premium.
Start your 7-day free trial.

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.

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

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

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 ?

Experts Exchange Solution brought to you by

Your issues matter to us.

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

Start your 7-day free trial>> 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)

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

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

Algorithms

From novice to tech pro — start learning today.

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with Premium.
Start your 7-day free trial.

> Second Function :

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

I don't think that's right