Question

What is the time complexity ?

int fact(int n)

{ if( n==1)

{return 1;}

n=n*fact(n-1);

return n;

}

Answer #1

The given function is

```
int fact(int n)
{
if (n == 1)
{
return 1;
}
n = n * fact(n - 1);
return n;
}
```

This is a program to calculate factorial.

Time complexity when parameter passed is 1

when 1 is passed it returns 1, and it includes only one comparision i..e if(n == 1) , nothing else is executed

So

T(1) = 1

Calculating T(n)

When any number is passed below opeations are done

time for one comparison(if (n==1)), time for one multiplication(n * fact(n-1)), time for one subtraction(n - 1)

and time for fact(n-1)

so

T(n) = T(n-1) + 3

= T(n-2) + 3 + 3 = T(n - 2) + 2*3

= T(n - 3) + 3 + 3 + 3 = T(n - 3) + 3*3

= T(n - k) + k * 3 = T(n-k) + 3k

T(1) = 1

if we put

n - k = 1

k = n + 1

T(n) = T(n - n + 1) + 3(n + 1)

= T(1) + 3n + 3

= 1 + 3n + 3

= 3n + 4

= O(n)

So O(n) is answer

What does the following function compute? Give an analysis of
its complexity
int fun1 (int n)
{
if (n == 0)
return
1;
else
return fun1(n-1) + fun1(n-1);
}

Determine the order of complexity for the following
algorithm:
function(int n) {
int l, u, m;
l=0; u= n-1;
while (l<u) {
m= (l+u)/2;
if (a[m] < x) l= m+1;
else if (a[m] >x) u=m-1;
else return
“found”
}
return (“not found”);
}

Given the following function:
int bar(int n) {
if( n < 0 )
return -2;
else if (n <= 1)
return 2;
else
return (3 + bar(n-1) +
bar(n-2));
}
What is returned by bar (4)? Show all the steps

Fact 1) int(E) is open.
Fact 2) int(E) is the largest (with respect to subsets) open set
that contains E.

Given the following function:
int C(int n,
int k)
{
if (k= =0) return 1;
else return (C(n-1, k-1) *
n)/k;
}
What type of function is this?
Recursive or Iterative. Explain your answer.

Assume that the functions CS303 and UMKC have been
defined as follows:
int CS303(int n) {
if (n == 0) {
return 1;
} else {
return UMKC(2, CS303(n - 1));
}
}
int UMKC(int n1, int n2) {
if (n1 == 0) {
return 0;
} else {
return n2 + UMKC(n1 - 1, n2);
}
}
What is the value of CS303(5)?

Assume that the functions CS303 and UMKC have been defined as
follows:
int CS303(int n) {
if (n == 0)
{
return
1;
} else {
return
UMKC(2, CS303(n - 1));
}
}
int UMKC(int n1, int n2) {
if (n1 == 0)
{
return
0;
} else {
return
n2 + UMKC(n1 - 1, n2);
}
}
What is the value of CS303(4)?

Draw a program flow graph for the function below
int binsearch(int x,int v[],int n)
{
int low,high,mid;
low=0;
high=n-1;
while(low<high)
{
mid = ( low + high ) / 2;
if( x < v[mid])
high = mid - 1;
else if ( x > v[mid])
low = mid + 1;
else
return mid;
}
return -1;
}

Assume that the functions CS303 and UMKC have been defined as
follows:
int CS303(int n) {
if (n <= 0) {
return 1;
} else {
return UMKC(5, CS303(n - 5));
}
}
int UMKC(int n1, int n2) {
if (n1 == 0) {
return 0;
} else {
return n2 + UMKC(n1/5, n2);
}
}
What is the value of CS303(20)?

Write down the run time of the following recursive functions as
a recurrence relation:
int f( int n ) {
if ( n <= 1 ) {
return 1;
}
return f( n – 1 ) + f( n – 1 );
}

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 4 minutes ago

asked 6 minutes ago

asked 6 minutes ago

asked 24 minutes ago

asked 34 minutes ago

asked 59 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 2 hours ago

asked 2 hours ago

asked 2 hours ago

asked 2 hours ago