Question

Which search method has logarithmic complexity?

• A. Linear search
• B. Binary search
• C. Sequential search
• D. None

Hint:

Logarithmic search space reduction (halving at each step) always indicates a logarithmic time complexity of \(O(\log n)\). Ensure the dataset is sorted before applying binary search!

Answer 1

The Correct Option is B

Step 1: Understanding the Question:
The question asks us to identify the search algorithm that possesses a time complexity of \(O(\log n)\) (logarithmic complexity).

Step 2: Key Formula or Approach:
The time complexity of an algorithm measures the relationship between the input size \(n\) and the number of operations performed. Logarithmic complexity is represented as \(O(\log n)\).

Step 3: Detailed Explanation:
$\bullet$ Linear search and sequential search are identical algorithms that scan a list from the first element to the last, resulting in a linear time complexity of \(O(n)\).
$\bullet$ Binary search works on a sorted array by repeatedly dividing the search interval in half.
$\bullet$ At each step, the algorithm compares the target value with the middle element of the array.
$\bullet$ If the target is smaller, the search continues in the left half; if larger, it continues in the right half.
$\bullet$ This step-by-step halving of the search space means that for an array of size \(n\), the maximum number of comparisons required is \(\log_2 n\).
$\bullet$ Mathematically, this reduction is modeled by the recurrence relation \(T(n) = T(n/2) + c\), which solves to \(T(n) = O(\log n)\) using the Master Theorem.
$\bullet$ This logarithmic behavior makes binary search exceptionally fast even for extremely large datasets.

Step 4: Final Answer:
Therefore, binary search has a logarithmic complexity of \(O(\log n)\), which matches option (B).