Question

Suppose you can use a library that contains two familiar sorting functions:
BUBBLESORT(A) and MERGESORT(A)
Both functions take as input an array A of length n and sort it. Their running times are O(n2) and O(n log n) respectively. The library also contains another sorting function, with the following pseudocode:

- function STRANGESORT(A)
- if (length(A)1000) then
- return BUBBLESORT(A)
- else
- return MERGESORT(A)
What is the worst-case running time of STRANGESORT? Please justify your answer.

Answer 1

First, find the worst case of Bubble Sort and MergeSort

Worst case of bubble sort is: n^2

Worst case of merge sort is: n*log(n)

Worst case of conditional algorithm means, the set of branch of algorithm (only one will select based on some condition), which ever take more time is consider as the worst case of whole algorithm.

If an algorithm consist of two branch (branch by conditions), and only one branch selected for execution, then the largest worst case among both branch worst case, will consider as algorithm worst case.

And the same rule apply for best case or average case.

In the above scenario, bubble sort has highest time complexity in worst case, so the strange sort worst case will be bubble sort worst case.

So, STRANGESORT worst case is: n^2