# YOU CAN DOWNLOAD 200+ SUBJECTS PDF BOOK FOR COMPETITIVE EXAMINATIONS

## Bottom-Up Mergesort Multiple choice Questions and Answers (MCQs)

Question 1 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

Merge sort uses which of the following algorithm to implement sorting?

backtracking | |

greedy algorithm | |

divide and conquer | |

dynamic programming |

Question 1 Explanation:

Merge sort uses the technique of divide and conquer in order to sort a given array. It divides the array into two halves and applies merge sort algorithm to each half individually after which the sorted versions of these halves are merged together.

Question 2 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

What is the average case time complexity of standard merge sort?

O(n log n) | |

O(n ^{2}) | |

O(n ^{2} log n) | |

O(n log n ^{2}) |

Question 2 Explanation:

The recurrence relation for merge sort is given by T(n) = 2T(n/2) + n. This can be solved using master's theorem and is found equal to O(n log n).

Question 3 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

What is the auxiliary space complexity of standard merge sort?

O(1) | |

O(log n) | |

O(n) | |

O(n log n) |

Question 3 Explanation:

The merging of two sorted arrays requires an additional space of n due to which the auxiliary space requirement of merge sort is O(n). Thus merge sort is not an in place sorting algorithm.

Question 4 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

What is the auxiliary space complexity of bottom up merge sort?

O(1) | |

O(n) | |

O(log n) | |

O(n log n) |

Question 4 Explanation:

The auxiliary space complexity of bottom up merge sort is same as standard merge sort as both uses the same algorithm for merging the sorted arrays which takes o(n) space. But bottom up merge sort does not need to maintain a call stack.

Question 5 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

What is the average time complexity of bottom up merge sort?

O(n log n) | |

O(n ^{2}) | |

O(n ^{2} log n) | |

O(n log n ^{2}) |

Question 5 Explanation:

The merge function in the bottom up merge sort takes O(n) time which is placed inside the for loop. The loop runs for O(log n) time, thus the overall time complexity of the code becomes O(n log n).

There are 5 questions to complete.