Algorithm Analysis/Merge Sort - Revision history

Admin: Automated edit (via update-page on MediaWiki MCP Server)

2026-06-05T23:16:57Z

Automated edit (via update-page on MediaWiki MCP Server)

← Older revision		Revision as of 23:16, 5 June 2026
Line 1:		Line 1:


	=Master Theorem Analysis=		=Master Theorem Analysis=

Line 22:		Line 24:

	<math>		<math>
	f(n) = \Theta \left( n^{\log_b{(a)}}) \log^{k}{(x)} \right)		f(n) = \Theta \left( n^{\log_b{(a)}} \log^{k}{(x)} \right)
	</math>		</math>

Admin: /* Master Theorem Analysis */

2017-07-20T10:12:21Z

Master Theorem Analysis

← Older revision		Revision as of 10:12, 20 July 2017
Line 7:		Line 7:
	</math>		</math>

	~~Because~~ the work done merging (the f(n) on the right) is linear, <math>f(n) = O(n)</math>.		due to the fact that each split operation splits the array of data into 2 parts of size <math>\frac{n}{2}</math>.

			The work done merging (the f(n) on the right) is linear, so <math>f(n) = O(n)</math>.

	Now we can apply the [[Master Theorem]]. The quantity c is:		Now we can apply the [[Master Theorem]]. The quantity c is:
Line 34:		Line 36:
	T(n) = \Theta( n \log{n} )		T(n) = \Theta( n \log{n} )
	</math>		</math>


	=Flags=		=Flags=

Admin at 10:11, 20 July 2017

2017-07-20T10:11:37Z

← Older revision		Revision as of 10:11, 20 July 2017
Line 1:		Line 1:
			=Master Theorem Analysis=

	Merge sort has the recurrence relation:		Merge sort has the recurrence relation:

Admin: Created page with "Merge sort has the recurrence relation: $T(n) = 2 T \left( \frac{n}{2} \right) + f(n)$ Because the work done merging (the f(n) on the right) is linear, $f(..."$

2017-07-20T10:11:25Z

Created page with "Merge sort has the recurrence relation: <math> T(n) = 2 T \left( \frac{n}{2} \right) + f(n) </math> Because the work done merging (the f(n) on the right) is linear, <math>f(..."

New page

Merge sort has the recurrence relation:

<math>
T(n) = 2 T \left( \frac{n}{2} \right) + f(n)
</math>

Because the work done merging (the f(n) on the right) is linear, <math>f(n) = O(n)</math>.

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

<math>
c = \log_b{(a)} = \log_2{(2)} = 1
</math>

Therefore <math>O(n^c) = O(n)</math>

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

<math>
f(n) = \Theta \left( n^{\log_b{(a)}}) \log^{k}{(x)} \right)
</math>

with k = 0. Then that implies:

<math>
T(n) = \Theta(n \log^{k+1}{(n)})
</math>

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

<math>
T(n) = \Theta( n \log{n} )
</math>

=Flags=

{{AlgorithmsFlag}}

[[Category:Algorithms]]
[[Category:Master Theorem]]
[[Category:Sort]]
[[Category:Merge Sort]]
[[Category:Algorithm Analysis]]

Algorithm Analysis/Merge Sort - Revision history

Admin: Automated edit (via update-page on MediaWiki MCP Server)

Admin: /* Master Theorem Analysis */

Admin at 10:11, 20 July 2017

Admin: Created page with "Merge sort has the recurrence relation: T(n) = 2 T \left( \frac{n}{2} \right) + f(n) Because the work done merging (the f(n) on the right) is linear, f(..."

Admin: Created page with "Merge sort has the recurrence relation: $T(n) = 2 T \left( \frac{n}{2} \right) + f(n)$ Because the work done merging (the f(n) on the right) is linear, $f(..."$