Data Structures and Algorithms MCQ - Performance Analysis of Algorithms and Recurrences

46 Consider the following C function:

double foo(int n)
{
int i;
double sum;
if (n = = 0) return 1.0;
else
{
sum = 0.0;
for (i = 0; i < n ; i ++)
sum + = foo(i);
return sum;
}
}
The space complexity of the above function is

Here foo(1) is recursive function. Spare complexity is O (n) as there can be at most O (n) active function at a time

47 Consider the following C function:

double foo(int n)
{
int i;
double sum;
if (n = = 0) return 1.0;
else
{
sum = 0.0;
for (i = 0; i < n ; i ++)
sum + = foo(i);
return sum;
}
}
The space complexity of the above function is foo() and store the values of foo(i), 0 < = i < n, as and when they are computed. With this modification, the time complexity for function foo() is significantly reduced. The space complexity of the modified function would be

Space complexity is O (n). The space we need array of size O (n). The space required for recursive call would be O (1) as the value would be taken from array again & again

48 Consider the following C-program fragment in which i, j, and n are integer variables.
for(i = n, j = 0; i > 0; i/ = 2, j + = i);
Let val (j) = denote the value stored in the variable j after termination of the for loop. Which one of the following is true?

If n is a power of 2, then

term
If n is not a power of 2, then there will be minor differences of 1 at

wherever

is odd.
Hence val(j) computed on the basis of n = 2ⁿ will give a fair answer

= 2(n – 1) = θ(n)

49 Consider the following recurrence
T(n) = 2T([√n]) + 1,T(1) = 1
Which one of the following is true?

T(n) = 2T(√n) + 1
Put n = 2^k
T(2^k) = 2T(n^k/2) + 1
replace T(2^k) by S(k)
S(k) = 2 S(k/2) + 1
Apply masters
K^log₂² ⇒ k > 1
So Θ(k)
Now we know n = 2^k, k = log₂(n)
then Θ(logn)

50 Consider the following segment of C code
int j, n;
j = i;
while (j < = n)
j = j*2;
The number of comparisons made in the execution of the loop for any n > 0 is

Since, j increases in power of 2's.
if statement j = j * 2 executes k times, then
2^k < n
⇒ k < log₂ n
Since k will be integer,
total number of comparison

(when loop exits)