Data Structures and Algorithms MCQ - 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

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

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?

The expected number of comparison is n.

33 The running time of the following algorithm

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

;
is best described by

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).

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?

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ⁿ).

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

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

Hence S = e^x