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

31. In the worst case, the number of comparisons needed to search singly linked list of length n for a given element is

Answer
Comment
Array

Option : D
Explanation :
The worst case number of comparison is n. to search any element from singly link list.

You must be logged in to post a comment.

You must be logged in to post a comment.

32. Consider the following algorithm for searching for a given number x in an unsorted array A[1 .......n] having n distinct values:
1. Choose an i uniformly at random from 1.. .n;
2. If A[i] = x then Stop else Goto 1;
Assuming that x is present on A, what is the expected number of comparisons made by the algorithm before it terminates?

Answer
Comment
Array

Option : A
Explanation : The expected number of comparison is n.

You must be logged in to post a comment.

You must be logged in to post a comment.

33. The running time of the following algorithm

Procedure A(n)
If n < = 2 return (1) else return

;
is best described by

Answer
Comment
Array

Option : C
Explanation :
Recurrance relation for procedure A (n) is
T(n) = T √n + 1 if n > 2
T(n) = 1 if n ≤ 2
T(n) = 1
Now, T (n) = T √n + 1
Put n = 2^k, T (2^k)= T (2^k/2) + 1
Use S(K) for T (2^k) then
S(K) = S(k/2) + 1
Apply masters method.
K^log21 ≅ 1
So θ (log k)
Now we know that
n = 2^k so, k= log₂n
So, O(log logn).

You must be logged in to post a comment.

You must be logged in to post a comment.

34. Consider the following three claims
l. (n + k)^m = Θ(n^m), where k and m are constants
2. 2^{n + 1} = O(2ⁿ)
3. 2^{2n + 1} = O(2ⁿ)
Which of these claims are correct?

Answer
Comment
Array

Option : A
Explanation :
Note:- In devotion place change first point by
1. (n+k)^m = O(n^m), where k and m are constants.
1. (n+k)m ≅ O (nm) because k & m are constant
then growth rate of both the function is same.
2. 2ⁿ⁺¹ ⇒ 2.2ⁿ, Here 2 is constant
So function is 2ⁿ. Statement is true.
3. 2²ⁿ⁺¹ ⇒ 2.2²ⁿ ⇒ 2.4ⁿ
So 4ⁿ > 2ⁿ then 2²ⁿ⁺¹ ≠ O(2ⁿ).

You must be logged in to post a comment.

You must be logged in to post a comment.

35. Consider the following C function.

float f (float x, int y)
{
float p, s; int i;
for (s = 1, p = 1, i = 1; i < y; i ++)
{
p* = x/i;
s + = p;
}
return s;
}
For large values of y, the return value of the function f best approximates

Answer
Comment
Array

Option : B
Explanation :
For large value of y
P = P * (x/i)
S = S + P
When i < y and i + +

Hence S = e^x

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.