0 votes 0 votes what is the recurrence relation for merge sort? Algorithms merge-sort algorithms time-complexity recurrence-relation sorting divide-and-conquer + – aditi19 asked Oct 6, 2018 aditi19 1.1k views answer comment Share Follow See 1 comment See all 1 1 comment reply MiNiPanda commented Oct 6, 2018 reply Follow Share T(n)= 2T(n/2) +Theta(n) 1 votes 1 votes Please log in or register to add a comment.
0 votes 0 votes First merge sort for half array(1to m) that takes T(n/2) Second merge sort for last half array(m+1to n) Final phase merging them in O(n) time So total time complexity=2T(n/2)+O(n/2) =O(nlogn) Ram Swaroop answered Mar 15, 2019 Ram Swaroop comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Reccurrence relation for merge sort is T(n)=2T(n/2)+O(n) Sanandan answered Sep 12, 2020 Sanandan comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes T(n) =2T(n/2) + O(n) T(1) = 1 Because in mergesort function we call two time mergesort and at last we call merge procedure , merge procedure take O(n) and each time we divide array in half . Aniket1710 answered Jul 10, 2023 Aniket1710 comment Share Follow See all 0 reply Please log in or register to add a comment.