The Gateway to Computer Science Excellence
0 votes
200 views
what is the recurrence relation for merge sort?
in Algorithms by Loyal | 200 views
+1
T(n)= 2T(n/2) +Theta(n)

2 Answers

+1 vote

Time Complexity: Merge Sort is a recursive algorithm and time complexity can be expressed as following recurrence relation.
T(n) = 2(n/2) + O(n)

​​​​​​​

by Active
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)
by Loyal
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,222 questions
59,847 answers
201,030 comments
118,094 users