Question

Time complexity of Merge Sort Algorithm and Binary Search Algorithm are respectively:
1. O(log₂ n) and O(n log₂ n)
2. O(n log₂ n) and O(log₂ n)
3. O(n²) and O(log₂ n)
4. O(2ⁿ) and O(n²)

Answer 1

Correct Answer - Option 2 : O(n log₂ n) and O(log₂ n)

Merge sort 

It is based on the divide and conquers approach.

Recurrence relation for merge sort will become:

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

Using Master’s theorem

T (n) = n × log₂n

Therefore, the time complexity of Merge Sort is θ(nlogn).

Binary Search

Search a sorted array by repeatedly dividing the search interval in half.

Recurrence for binary search is T(n) = T(n/2) + θ(1)

Using Master’s theorem

T (n) = log₂n

Consider only half of the input list and throw out the other half. Hence time complexity is O(log n).