Master Method in DAA


The master method is a recurrence-solving cookbook approach. Although it cannot handle all recurrences, it is quite useful for dealing with a large number of recurrences seen in practice. Assume there is a recurrence of the form:

T(n) = aT(n/b)+â(n)

where a and b are random constants, and â is a function of n. This recurrence would occur in the analysis of a recursive algorithm that separates huge inputs of size n into n/b sub-problems, solves the sub-problems recursively, and then recombines the results. Splitting the problem into sub-problems and recombining the solutions is â(n).

Master Theorem

Master Theorem

This theorem is used to support the master approach. Let a>=1 and b>1 be constants, â(n) be a function, and T(n) be a recurrence function defined on non-negative integers.

T(n) = aT(n/b) + â(n)

where n/b might be taken as either n/b or n/b. Then T(n) can be asymptotically confined as follows:

Case 1: T(n)=θ(nlogba) if â(n)=O(nlogba-ϵ) for some constant ϵ>0.

Case 2: T(n)=(nlogbalg n) if â(n) = (nlogba)

Case 3: T(n)=(â(n)) if â(n)=Ω(nlogba+ϵ) for some constant ϵ>0 and aâ(n/b)≤câ(n) for some constant c<1 and all sufficiently big n.

Let’s take the time to attempt to comprehend what the master theorem states before applying it to specific situations. In each of the three cases, the function â(n) is compared to the function nlogba. The greater of these two functions(â(n) & nlogba), determines the solution to the recurrence. If the function nlogba is the bigger, like in case 1, the answer will be T(n)=θ(â(nlogba). If the function â(n) is greater, as in case 3, the answer will T(n)=θ(â(n)). If the two functions have the same size, as in case 2, we multiply by a logarithmic factor, yielding T(n)=θ(nlogba lg n)=(â(n)lg n).

Technicalities of Master Method

There are several technicalities that must be grasped in addition to intuition.

  1. In the first case, â(n) must be polynomially less than nlogba. That is, for some constant ϵ> 0, â(n) must be asymptotically less than nlogba by a factor of nϵ.
  2. In the third case, â(n) must not only be greater than nlogba, and it must also be polynomially bigger and meet the “regularity” criterion that aâ(n/b)≤câ(n). Most polynomially limited functions we’ll come across, satisfy this requirement.

It’s crucial to note that the three cases shown above don’t represent all of the options for â (n). When â(n) is less than nlogba but not polynomially smaller, there is a gap between examples 1 and 2. When â(n) is bigger than nlogba but not polynomially greater, there is a gap between cases 2 and 3. The master technique cannot be used to solve the recurrence if the function â(n) falls into one of these gaps, or if the regularity criterion in case 3 fails to hold.

How To Use Master Method

To apply the master method, we simply decide which case of the master theorem applies (if any) and record the result.

Example 1

Consider the following scenario:

Master Method Example1

We have a=9, b=3, â(n)=n for this recurrence, and consequently, nlogba=nlog39=θ(n2). As â(n)=0(nlog39-ϵ), where ϵ=1, we can use case 1 of the master theorem to determine that T(n)=θ(n2).

Example 2

Consider this:

Master Method Example2

nlogba=nlog3/21=n0=1, where a=1, b=3/2 and â(n)=1, as â(n)=θ(nlogba)=θ(1), Case 2 applies, and the solution to the recurrence is T(n)=θ(lg n).

Example 3

In the event of a recurrence,

Master Method Example3

here, a=3, b=4, â(n)=n lg n, and nlogba=nlog43=0(n0.793) are the values. Case 3 applies if we prove that the regularity criterion holds for â(n)=Ω(nlog43+ϵ), where ϵ0.2. (n). For c=3/4, aâ(n/b)=3(n/4)lg(n/4)≤(3/4)n lg n=câ(n) for sufficiently big n. As a result, T(n)=θ(n lg n).


Add Comment