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

If they are asking for worst case complexity hence,

By calling A(n) we get A(n/2) 5 times,

Hence by applying masters theorem,

Thus value of alpha will be 2.32

It is B. searching for only one half of the list. leading to T(n/2) + constant time in comparing and finding mid element.

According to Master theorem,

using master method (case 1)

We can apply Master's theorem case 1 with 

So,

So, only option possible is B.

We can also directly solve as follows:

OR

The complexity will be the number of times the recursion happens which is equal to the number of times we can take square root of n recursively, till n becomes 2.

 (We are taking floor of square root of numbers, and between
successive square roots number of numbers are in the series 3,5,7... like 3 numbers from 1...4,5numbers from 5-9 and so on). 

We can try out options here or solve as shown at end:

Put

So, answer must be B.

These are examples of some standard algorithms whose 
Merge Sort:    T(n) = 2T(n/2) + Θ(n). It falls in case 2 as c is 1 and Log_ba] is also 1 and  the solution is Θ(n Logn) //time complexity can be evaluated using Master Method

Binary Search: T(n) = T(n/2) + Θ(1). It also falls in case 2 as c is 0 and Log_ba is also 0 and the solution is Θ(Logn) //time complexity can be evaluated using Master Method

Quick Sort : Time taken by QuickSort in general can be written as  T(n) = T(k) + T(n-k-1) + (n)

Tower of Hanoi : T(n) = 2T(n-1) + 1

Option C it can be done by Master theorem.

So,

is true for any real

Hence Master theorem Case 1 satisfied,