Data Structures and Algorithms - Performance Analysis of Algorithms and Recurrences

Avatto > > UGC NET COMPUTER SCIENCE > > PRACTICE QUESTIONS > > Data Structures and Algorithms > > 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

Answer
Comment
Array

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

You must be logged in to post a comment.

You must be logged in to post a comment.

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

Answer
Comment
Array

Option : B
Explanation :
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

You must be logged in to post a comment.

You must be logged in to post a comment.

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?

Answer
Comment
Array

Option : C
Explanation :
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)

You must be logged in to post a comment.

You must be logged in to post a comment.

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

Answer
Comment
Array

Option : B
Explanation :
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)

You must be logged in to post a comment.

You must be logged in to post a comment.

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

A
B
n
C
D

Answer
Comment
Array

Option : D
Explanation :
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)

You must be logged in to post a comment.

You must be logged in to post a comment.

Related Quiz.
Performance Analysis of Algorithms and Recurrences

Forgot your password?

I agree with the Terms.