Hi everyone, next series I will present about Divide and Conquer algorithm.
1.22 Master Theorem for Divide and Conquer Recurrence
All Divide and Conquer algorithms (which we will discuss in detail in the Divide and Conquer chapter) divide the problem into subproblems, each of which is part of the original problem, and then do some work. added to calculate the final answer.
For example, the Merge sort algorithm (which I’ll cover in more detail in the Sort chapter) works on two subproblems , each as small as half the size of the original T(n/2) problem , and then do O(n) extra work to merge .
=> This gives the equation for running time:
The following theorem can be used to determine the runtime of divide and conquer.
For a given program (algorithm), we first try to find the repetition relationship for the problem.
If the repetition is like below then we can directly give the answer without solving it completely.
where a ≥ 1, b > 1, k ≥ 0 and b being a real number , then:
- If a > b^k
- If a = b^k
- a. If p > -1
- b. If p = –1
- c. If p < -1
- If a < b^k
- a. If p ≥ 0
- b. If p < 0
The theorem is really complicated, I would like to stop at the level of using the theorem and applying it, if you have a deeper passion for math and want to prove the theorem, you can refer to the following link (or google search for more information). please help me:
[ https://www.cs.purdue.edu/homes/spa/papers/jacm-divide.pdf ]
1.23 Divide and Conquer Master Theorem: Problems & Solutions
For each of the following problems, give an expression for the running time T(n) if it can be solved by Master Theorem.
If not, indicate that Master Theorem does not apply.
Problem-1
T(n) = 3T(n/2) + n^2
Solution : You find from the expression of variables a, b, k, p and then check if it belongs to the case in Master Theorem, you will apply the same in the following lessons.
Explain details:
We have a=3, b=2, k=2, p=0(Because n^2 = n^2 * 1 = n^2 * (1 any expression)^0 )
⇒ 3 < 2^2 and p = 0 ⇒ T(n) = Θ(n^2) (Master Theorem Case 3.a)
Problem-2 T(n) = 4T (n/2) + n^2
Solution : T(n) = 4T (n/2) + n^2 ⇒ T (n) = Θ(n^2 * logn) (Master Theorem Case 2.a)
Problem-3 T(n) = T(n/2) + n 2
Solution : T(n) = T(n/2) + n^2 ⇒ Θ(n^2) (Master Theorem Case 3.a)
Problem-4 T(n) = 2^n * T(n/2) + n^n
Solution : T(n) = 2^n T(n/2) + nn ⇒ Not applicable because a is not a constant)
Problem-5 T(n) = 16T(n/4) + n
Solution : T(n) = 16T (n/4) + n ⇒ T(n) = Θ(n^2) (Master Theorem Case 1)
From here, the exponential symbols in the log function are a bit difficult to represent on viblo, so I would like to use pictures
This article is a bit heavy on math, it is a general theory for divide-and-conquer algorithms. In later chapters, more specific problems will be applied to calculate the complexity of the algorithm.