Question

Suppose that you sort a large array of integers by using a merge sort. Next you use a binary search to determine whether a given integer occurs in the array. Finally, you display all of the integers in the sorted array. a. Which algorithm is faster, in general: the merge sort or the binary search? Explain in terms of Big O notation. b. Which algorithm is faster, in general: the binary search or displaying the integers? Explain in terms of Big O notation.

Answer 1

Answer:

See explaination

Explanation:

Merge sort working-

1.type of recursive sorting algorithm.

2.divides given array into halves.

3. Sort each halves. Merge this halves to give a sorted array.

4. Recursive call continues till array is divided and each piece has only one element.

5. Merge this small pieces to get a sorted array.

Binary search-

1. It is a search algorithm.

2. Requires a sorted array to work on.

3.Works repetively dividing a half portion of list that could contain item until it has narrowed down the possible location to just one.

Comparing Merge sort and Binary Search using Big O notation-

Merge Sort - O(n*log(n)) in all scenario whether best, average or worst case.

Binary Search- O(log(n)) in average and worst case. O(1) in best case.

So seeing the above comparison Binary search is faster.

Comparing Binary search and displaying the integers-

Binary Search- O(log(n)) in average and worst case. O(1) in best case.

Displaying the integer-O(1) if already initialized, O(n) in case of loop or function.

So seeing above one can conclude that binary search is fast. But in best case both works in a similar manner.