Advanced master theorem for divide-and-conquer recursion

Divide and Conquer is an algorithm based on recursively decomposing a problem into multiple sub-problems of similar type, and these sub-problems can be easily solved.

Example

Let us take an example to understand the divide and conquer technique more deeply -

function recursive(input x size n)
   if(n < k)
      Divide the input into m subproblems of size n/p.
      and call f recursively of each sub problem
   else
      Solve x and return

Combine the results of all subproblems and return the solution to the original problem.

Explanation − In the above problem, the problem set is to be subdivided into smaller subproblems that can be solved easily.

Masters Theorem for divide and conquer is an analysis theorem that can be used to determine a big-0 value for recursive relation algorithms. It is used to find the time required by the algorithm and represent it in asymptotic notation form.

Example of runtime value of the problem in the above example −

T(n) = f(n) + m.T(n/p)

For most of the recursive algorithm, you will be able to find the Time complexity For the algorithm using the master's theorem, but there are some cases master's theorem may not be applicable. These are the cases in which the master's theorem is not applicable. When the problem T(n) is not monotone, for example, T(n) = sin n. Problem function f(n) is not a polynomial.

As the master theorem to find time complexity is not hot efficient in these cases, and advanced master theorem for recursive recurrence was designed. It is designed to handle recurrence problem of the form −

T(n) = aT(n/b) + ø((n^k)logpn)

where n is the scale of the problem.

a = number of subproblems in the recursion, a > 0

n/b = size of each subproblem b > 1, k >= 0, p is a real number.

To solve this type of problem we will use the following solution:

• If a > b_k, then T(n) = ∅ ( nlogba)
• If a = b_k, then
  • If p > -1, then T(n) = ∅(nlogba log^{p 1}n)
  • If p = -1, then T(n) = ∅(nlog_ba loglogn)
  • If p ba)
• If a k, then
  • if p > = 0 , then T(n) = ∅(n_klog_pn)
  • If p

Using the high-level master algorithm, we will calculate the complexity of some algorithms −

Binary search − t(n) = θ( logn)

Merge sort − T(n) = θ(nlogn)

The above is the detailed content of Advanced master theorem for divide-and-conquer recursion. For more information, please follow other related articles on the PHP Chinese website!