| | |

Question: Mergesort is a sorting algorithm where the running time is in Θ(nlogn), in the best-case, and is in Θ(n2), in the worst-case – Free Chegg Question Answer

Flag

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:

free chegg question answer
Smart Teacher From Answerie.com
Answer:

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

Free Chegg Question Answer

Leave a Reply

Your email address will not be published. Required fields are marked *