Algorithm Analysis/Merge Sort

Master Theorem Analysis

Merge sort has the recurrence relation:

$T(n)=2T\left({\frac {n}{2}}\right)+f(n)$

due to the fact that each split operation splits the array of data into 2 parts of size Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \frac{n}{2}} .

The work done merging (the f(n) on the right) is linear, so Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle f(n) = O(n)} .

Now we can apply the Master Theorem. The quantity c is:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c = \log_b{(a)} = \log_2{(2)} = 1 }

Therefore Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle O(n^c) = O(n)}

If we examine the 3 cases, we can see that we fall into Case 2:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle f(n) = \Theta \left( n^{\log_b{(a)}}) \log^{k}{(x)} \right) }

with k = 0. Then that implies:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle T(n) = \Theta(n \log^{k+1}{(n)}) }

Therefore, overall, merge sort is Theta(n log n):

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle T(n) = \Theta( n \log{n} ) }