Solved

# RunTime Complexity

Posted on 2007-04-09

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