Q54: Linear search’s recursive equation

Question #54: Which of the following recursive equation holds true for the linear search algorithm?

Options:

1. T(n) = T(n-1) + 1
2. T(n) = T(n/2) + 1
3. T(n) = 2T(n/2) + 1
4. T(n) = T(log(n)) + 1

Solution: In every step while searching linearly, we eliminate one element from the list. Hence the problem T(n) reduces to T(n-1). Therefore, option 1 is correct.

Q48: Solve recursive equation

Question #48: What will be the time complexity of the following recurrence relation?

T(n) = 2T(n/2) +1

 

Options:

1. O(log(n))
2. O(n)
3. O(nlog(n))
4. O(n²)

 

Solution:

We can expand the recurrence relation above as follows:

T(n) = 2T(n/2) + 1

T(n) = 2( 2T(n/4) +1) + 1 = 4T(n/4) +2 + 1

T(n) = 8T(n/8) +3 + 2 + 1

And so on..

Finally, the relation will look like this: (1+2+4+8+16+…+n/2) having totally log(n) terms, which after applying GP sum evaluates to ‘n’. Hence, the correct answer is option 2.

Q13: Time complexity of binary search algorithm

Question #13: Which of the following recursive equation holds true for the binary search algorithm?

Options:

1. T(n) = T(n-1) + 1
2. T(n) = T(n/2) + 1
3. T(n) = 2T(n/2) +1
4. T(n) = T(log(n)) +1

 

Solution:

After every step, the problem gets reduced to half the original size since the number we search lies in either first half or second half. See the following example:

This gets evaluated to:

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

=> T(n) = T(n/4) + 1 + 1

=> T(n) = T(n/8) + 1 + 1 + 1

=>T(n) = log(n) + constant

Hence, the correct answer is option 2.