Master Theorem Examples
Let’s understand examples related to the master theorem.. We’ll solve some examples from each case.
Examples
The following are some examples of the master theorem. Let’s look at them one by one.
Example 1
This is the case of merge sort. Its time complexity is = + .
Solution
In this example, and are both equal to 2. So, = = 1 which means that = n = . That means case 2 is applied and = . Its final time complexity is = .
Example 2
This is a case of binary search. Its time complexity is = + .
Solution
In this example, is equal to 1 and is equal to 2. So, = = 0 which means that = k = . That means case 2 is applied and = . Its final time complexity is = .
Example 3
This is a case of binary tree traversal. Its time complexity is = 2 + .
Solution
In this example, is equal to 2 and is also equal to 2. So, = = 1 which means that = k = . That means case 1 is applied and = . Its final time complexity is = .
Example 4
In this example, an algorithm has a time complexity of = 2 + .
Solution
In this example, is equal to 2 and is also equal to 2. So, = = 1 which means that = = . That means case 3 is applied and = . Its final time complexity is = .