Test: Recurrence & Searching- 2 - Computer Science Engineering (CSE) MCQ

 ( Putting 2so that we can take log. one more step of recurrence can't change the complexcity   

0 1 -2
01 10 11 -3
010 011 101 110 111 -5
0101 0110 0111 1010 1011 1101 1110 1111 -8

So, x_n = x_n-1 + x_n-2 (For all the strings ending in 1, we get two new strings and for all strings ending in 0, we get a new string. So, the new set of strings for n+1, will have exactly n strings ending in 1)

x₅ = 8+5 = 13

Number of binary strings of length n that contain no consecutive 0s, following will be the required recurrence relation:

T(n) = T(n-1) + T(n-2) n>2

base condition T(1) = 2 and T(2) = 3

T(1) =2 There will be 2 strings of length 1, i.e 0 & 1
T(2) =3 There will be 3 strings of length 2, i.e. 01,10,11

T(3) = T(1) + T(2) = 2+3 = 5
T(4) = T(3) + T(2) = 5 + 3 = 8
T(5) = T(4) +T(3) = 8 + 5 = 13

If we use Master theorem we get option B. But one must know that Matser theorem is used to find the asymptotic bound and not an EXACT value. And in the question here it explicitly says "evaluates to".

To, check Master theorem case 3, we need C>0

So using case three of master theorem

Recurrence relation for Towers of Hanoi is
T(1) = 1
T(n) = 2 T( n-1 ) +1
So Answer should be (D)

we can take any ε from 0-1 for example 0.5 which gives  whose proof
is given here: http://math.stackexchange.com/questions/145739/prove-that-logn-o-sqrtn 

Counting the number of bit strings NOT containing two consecutive 1's. (It is easy to derive a recurrence relation for the NOT case as shown below.)

0 1
00 01 10 - 3 (append both 0 and 1 to any string ending in 0, and append 0 to any string ending in 1)

000 001 010 100 101 - 5 (all strings ending in 0 give two strings and those ending in 1 give 1 string)

0000 0001 0010 0100 0101 1000 1001 1010 - 8

....

a_n' = a_n-1' + a_n-2' (where an denote the number of bit strings of length n containing two consecutive 1s)

2ⁿ - a_n = (2^n-1 - a_n-1) + (2^n-2 - a_n-2)

a_n = 2^n-2(4 - 2 - 1) + a_n-1 + a_n-2

a_n = a_n-1 + a_n-2 + 2^n-2

T(n) = T(n-1) + T(n-3) + 2, here T(n) denotes the number of times a recursive call is made for input n. 2 denotes the two direct recursive calls.

T(n<=0) = 0
T(1) = 2
T(2) = 4
T(3) = 6
T(4) = 10
T(5) = 16
T(6) = 24

So, answer is 24 + 1 call from main = 25.

Using case 1 of master method ,

Expected number of comparisons 

= 1x Probability of first element be x + 2 x Probability of second element be x + .... +n x Probability of last element be x.

when it is option C the control will continue to iterate as i=8 and j=9;

again and again i will be assigned k which itself equals 8 as 8+9/2 being stored in an integer type variable, will evaluate to 8

For option A, with X=9 , k will take the following values:

• 4
• 6
• 7
• 8 - y[8] = 9, x found

For option D, with X = 10, k will take the following values: 

• 4, y[4] = 10, x found

if( Y[k] < x) then i = k + 1;

if given element that we are searching is greater then searching will be continued upper half of array

otherwise j = k - 1;
lower half.
Take few case in consideration i.e.

1. all elements are same
2. increasing order with no repeatation
3. increasing order with repeatation.

We can simply use clever indexing to binary search the element in the odd positions, and in the even positions separately.

This will take O(logn) time andO(1) space in the worst case.

A: Sorting using Quicksort will take O(n²) time.

B: Merging will take O(n) time and O(n) space.

C: Binary search only works on a sorted array.

E: Sequential search will take O(n) time.