Which of the following algorithms has the smallest time complexity?
a. linear search
b. binary search
c. merge sort
d. insertion sort
c. merge sort
To determine the algorithm with the smallest time complexity among the given options, let's analyze the time complexities of each algorithm:
a. Linear search: In the worst case, linear search has a time complexity of O(n), where n is the size of the input array.
b. Binary search: In the worst case, binary search has a time complexity of O(log n), where n is the size of the input array. This is because binary search continually divides the search space in half.
c. Merge sort: Merge sort has a time complexity of O(n log n) in all cases. This is because the algorithm divides the input array into smaller sub-arrays, sorts them, and then merges them back together.
d. Insertion sort: In the worst case, insertion sort has a time complexity of O(n^2), where n is the size of the input array. This is because it repeatedly compares and shifts elements as it traverses the array.
Comparing the time complexities, we can conclude that the algorithm with the smallest time complexity among the given options is binary search with a time complexity of O(log n).