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

36 The cube root of a natural number n is defined as the largest natural number m such that m³ ≤ n. The complexity of computing the cube root of n (n is represented in binary notation) is

Use binary search in the array of number from 1 ........ n to check cube of the number matches n (i.e. a[i]* a [i]* a [i] = = n). option (C) is true

37 The tightest lower bound on the number of comparisons, in the worst case, for comparison based sorting is of the order of

The best complexity in worst case for any comparision based sorting technical cannot be less then nlogn.

38 What does the following algorithm approximate?

(Assume m > 1, ∈ > 0).
x = m ;
y = 1 ;
while (x – y > ∈)
{ x = (x + y) / 2 ;
y = m / x ;
}
print (x) ;

Given program fragment in Pseudo language is
x = m ;
y = 1 ;
while (x – y > e)
x = (x + y) /2 ;
y = m/x ;
}
Print (x)
This program will find out the square root of m, suppose that m = 2

X-	Y	X	Y
1st looping	2	3/2=1.5	2/1.5=1.33
2nd looping	.16	(1.5+1.3)/2 = 1.415	2.0/1.415 = 1.413
3rd looping	0.02	1.414	1.414
4th looping	0

as x – y = 0 exit from loop hence print 1.414 which is root of 2.

39 Let A [1,..., n] be an array storing a bit (1 or 0) at each location, and f(m) is a function whose time complexity is Θ(m). Consider the following

program fragment written in a C like language:

counter = 0;
for(i = 1; i < n; i++)
{
if (A[i] = = 1) counter ++;
else
{
f(counter);
counter = 0;
}
}
The complexity of this program fragment is

Case I :– if A = 0 0 0 0 0 0 0 ...
then always else part is execute so f (wanter) where counter = 0 is executed n times.
As given in clvestion complexity of f(o) is O (1) So O (1) + O (1)..... b times ⇒ O (n)
Case II : if A = [1, 1,.................1]
the loop execute n time and only if statment is executed hence complexity is O (n).
Case III : if A = [1,0,1,0,1,0..........]
or A = [0,1,0,1,0,1...................]
or any other case.
Both if and else is executed but every time when else part is executed counter is again set to O. Hence complexity is O (n).

40 The time complexity of the following C function is (assume n > 0)

int recursive (int n)
{
if (n = = 1)
return (1);
else
return(recursive(n-1)+ recursive(n-1));
}

Recurrence relation for function is
T (n) = 2 T (n – 1) + 1
= 2 [2T (n–2) + 1] + 1
= 4 T (n–2) + 2 + 1
= 4 [2T (n–3)+1] + 2 + 1
= 2³T (n–3) + 2² + 2 + 1
2k T (n–k) + 2^k-1 + ---2+1
put n–k = 1
So 2^n-1 T (1) + 2^n-2 + ----- 2 + 1
⇒ 2^n-1 + 2^n-2 + --- 2 + 1
⇒ 2^n-1 ⇒ O (2ⁿ).