Mergesort is a sorting algorithm where the running time is in Θ(nlogn), in the best-case, and is in Θ(n2), in the worst-case.
Is the above statement true or false + give an explanation for your response.
Transcribed text From Image:
Expert Chegg Question Answer:
Answer: -------- False Explanation: ------------- in every step of the merge sort, the array is split into exactly two halves, and work done is Θ(n) in each merge process so, the recurrence relation is T(n) = 2T(n/2) + Θ(n) T(n) = 2T(n/2) + n = 2(2T(n/4) + n/2) + n = 4T(n/4) + n + n = 4(2T(n/8) + n/4) + n + n = 8T(n/8) + n + n + n = n + ... + n + n + n (log n terms) = n log(n) so, T(n) is Θ(n log(n)) so, the time complexity is always Θ(n log n) in best case, worst case, and average case