Time complexity of Merge Sort Algorithm and Binary Search Algorithm are respectively............

Question

Accepted Answer

The correct option is (2):
$O(n \log\_{2}n)$ and $O(\log\_{2}n)$

Merge Sort is a highly efficient sorting algorithm that follows the **Divide and Conquer** paradigm. To calculate its time complexity, we consider the two main phases: the recursive division and the merging process. The division of the array into halves continues until the subarrays contain a single element, which results in $\log\_{2}n$ levels of recursion. Crucially, the *merging* of the sorted subarrays at each of these $\log\_{2}n$ levels requires linear time, $O(n)$, because every element must be processed and placed into the final sorted array. Therefore, the total time complexity for Merge Sort is the product of the levels and the work per level: $O(n \cdot \log\_{2}n)$. This performance is consistent across best, average, and worst cases because the algorithm always performs the complete division and merging steps, irrespective of the initial order of elements.

Binary Search is a highly efficient **search** algorithm that operates exclusively on a sorted array. Its efficiency is derived from its strategy of repeatedly cutting the search space in half. In each step, the algorithm compares the target value with the middle element of the current search interval and eliminates one full half of the data. This repeated halving of the input size $n$ means the number of comparisons required grows logarithmically. Specifically, reducing the problem size from $n$ to 1 takes $\log\_{2}n$ operations. Thus, the time complexity of Binary Search is $O(\log\_{2}n)$.

The incorrect option is (1):
This option, $O(\log\_{2}n)$ and $O(n \log\_{2}n)$, incorrectly reverses the complexities of the two algorithms. The complexity $O(\log\_{2}n)$ is characteristic of search algorithms that use a "halving" strategy, which is Binary Search. In contrast, the complexity $O(n \log\_{2}n)$ is typical for efficient, comparison-based sorting algorithms like Merge Sort. A sorting algorithm that must touch and potentially move all $n$ elements cannot achieve the faster logarithmic time of a search.

The incorrect option is (3):
This option proposes $O(n^2)$ and $O(\log\_{2}n)$. While the complexity for Binary Search, $O(\log\_{2}n)$, is correct, the complexity for Merge Sort, $O(n^2)$, is incorrect. $O(n^2)$ (quadratic time) is the worst-case performance for less optimal sorting methods like Insertion Sort or Bubble Sort. Merge Sort is asymptotically faster than quadratic sorting algorithms, with a consistent complexity of $O(n \log\_{2}n)$. The difference between $O(n \log\_{2}n)$ and $O(n^2)$ is significant for large datasets, making $O(n^2)$ an inaccurate description of Merge Sort's efficiency.

The incorrect option is (4):
This option, $O(2^n)$ and $O(n^2)$, is highly inaccurate for both algorithms. $O(2^n)$ represents **exponential** time complexity, which is reserved for algorithms that are computationally very expensive, often exploring a vast number of possibilities (e.g., brute-force solutions to NP-hard problems). Merge Sort is an efficient, practical algorithm and is never exponential. Furthermore, the $O(n^2)$ complexity proposed for Binary Search is drastically too slow, as Binary Search is known for its excellent logarithmic performance of $O(\log\_{2}n)$.