Trang chủ‎ > ‎IT‎ > ‎Programming‎ > ‎Algorithms Design‎ > ‎Big-O, Little-O, Theta, Omega‎ > ‎

Master Theorem - Complexity Analysis

Master theorem (analysis of algorithms)

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
For the result in enumerative combinatorics, see MacMahon Master theorem.
For the result about Mellin transforms, see Ramanujan's master theorem.

In the analysis of algorithms, the master theorem for divide-and-conquer recurrences provides an asymptotic analysis (using Big O notation) for recurrence relations of types that occur in the analysis of many divide and conquer algorithms. The approach was first presented by Jon Bentley, Dorothea Haken, and James B. Saxe in 1980, where it was described as a "unifying method" for solving such recurrences. The name "master theorem" was popularized by the widely used algorithms textbook Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein.

Not all recurrence relations can be solved with the use of this theorem; its generalizations include the Akra–Bazzi method.

Introduction

Consider a problem that can be solved using a recursive algorithm such as the following:

 procedure p( input x of size n ):
   if n < some constant k:
     Solve x directly without recursion
   else:
     Create a subproblems of x, each having size n/b
     Call procedure p recursively on each subproblem
     Combine the results from the subproblems

The above algorithm divides the problem into a number of subproblems recursively, each subproblem being of size n/b. Its call tree has a node for each recursive call, with the children of that node being the other calls made from that call. The leaves of the tree are the base cases of the recursion, the subproblems (of size less than k) that do not recurse. The above example would have a child nodes at each non-leaf node. Each node does an amount of work that corresponds to the size of the sub problem n passed to that instance of the recursive call and given by f ( n ) {\displaystyle f(n)} f(n). The total amount of work done by the entire algorithm is the sum of the work performed by all the nodes in the tree.

The runtime of an algorithm such as the 'p' above on an input of size 'n', usually denoted T ( n ) {\displaystyle T(n)} T(n), can be expressed by the recurrence relation

T ( n ) = a T ( n b ) + f ( n ) , {\displaystyle T(n)=a\;T\left({\frac {n}{b}}\right)+f(n),} {\displaystyle T(n)=a\;T\left({\frac {n}{b}}\right)+f(n),}

where f ( n ) {\displaystyle f(n)} {\displaystyle f(n)} is the time to create the subproblems and combine their results in the above procedure. This equation can be successively substituted into itself and expanded to obtain an expression for the total amount of work done. The master theorem allows many recurrence relations of this form to be converted to Θ-notation directly, without doing an expansion of the recursive relation.

Generic form

The master theorem often yields asymptotically tight bounds to some recurrences from divide and conquer algorithms that partition an input into smaller subproblems of equal sizes, solve the subproblems recursively, and then combine the subproblem solutions to give a solution to the original problem. The time for such an algorithm can be expressed by adding the work that they perform at the top level of their recursion (to divide the problems into subproblems and then combine the subproblem solutions) together with the time made in the recursive calls of the algorithm. If T ( n ) {\displaystyle T(n)} T(n) denotes the total time for the algorithm on an input of size n {\displaystyle n} n, and f ( n ) {\displaystyle f(n)} f(n) denotes the amount of time taken at the top level of the recurrence then the time can be expressed by a recurrence relation that takes the form:

T ( n ) = a T ( n b ) + f ( n ) {\displaystyle T(n)=a\;T\!\left({\frac {n}{b}}\right)+f(n)} T(n)=a\;T\!\left({\frac {n}{b}}\right)+f(n)

Here n {\displaystyle n} n is the size of an input problem, a {\displaystyle a} a is the number of subproblems in the recursion, and b {\displaystyle b} b is the factor by which the subproblem size is reduced in each recursive call. The theorem below also assumes that, as a base case for the recurrence, T ( n ) = Θ ( 1 ) {\displaystyle T(n)=\Theta (1)} {\displaystyle T(n)=\Theta (1)} when n {\displaystyle n} n is less than some bound κ > 0 {\displaystyle \kappa >0} \kappa > 0, the smallest input size that will lead to a recursive call.

Recurrences of this form often satisfy one of the three following regimes, based on how the work to split/recombine the problem f ( n ) {\displaystyle f(n)} f(n) relates to the critical exponent c crit = log b ⁡ a {\displaystyle c_{\operatorname {crit} }=\log _{b}a} {\displaystyle c_{\operatorname {crit} }=\log _{b}a}. (The table below uses standard big O notation.)

c crit = log b ⁡ a = log ⁡ ( # subproblems ) / log ⁡ ( relative subproblem size ) {\displaystyle c_{\operatorname {crit} }=\log _{b}a=\log(\#{\text{subproblems}})/\log({\text{relative subproblem size}})} {\displaystyle c_{\operatorname {crit} }=\log _{b}a=\log(\#{\text{subproblems}})/\log({\text{relative subproblem size}})}
Case Description Condition on f ( n ) {\displaystyle f(n)} f(n) in relation to c crit {\displaystyle c_{\operatorname {crit} }} {\displaystyle c_{\operatorname {crit} }}, i.e. log b ⁡ a {\displaystyle \log _{b}a} {\displaystyle \log _{b}a} Master Theorem bound Notational examples
1 Work to split/recombine a problem is dwarfed by subproblems.

i.e. the recursion tree is leaf-heavy

When f ( n ) = O ( n c ) {\displaystyle f(n)=O(n^{c})} {\displaystyle f(n)=O(n^{c})} where c < c crit {\displaystyle c<c_{\operatorname {crit} }} {\displaystyle c<c_{\operatorname {crit} }}

(upper-bounded by a lesser exponent polynomial)

... then T ( n ) = Θ ( n c crit ) {\displaystyle T(n)=\Theta \left(n^{c_{\operatorname {crit} }}\right)} {\displaystyle T(n)=\Theta \left(n^{c_{\operatorname {crit} }}\right)}

(The splitting term does not appear; the recursive tree structure dominates.)

If b = a 2 {\displaystyle b=a^{2}} {\displaystyle b=a^{2}} and f ( n ) = O ( n 1 / 2 − ϵ ) {\displaystyle f(n)=O(n^{1/2-\epsilon })} {\displaystyle f(n)=O(n^{1/2-\epsilon })}, then T ( n ) = Θ ( n 1 / 2 ) {\displaystyle T(n)=\Theta (n^{1/2})} {\displaystyle T(n)=\Theta (n^{1/2})}.
2 Work to split/recombine a problem is comparable to subproblems. When f ( n ) = Θ ( n c crit log k ⁡ n ) {\displaystyle f(n)=\Theta (n^{c_{\operatorname {crit} }}\log ^{k}n)} {\displaystyle f(n)=\Theta (n^{c_{\operatorname {crit} }}\log ^{k}n)} for any k ≥ 0 {\displaystyle k\geq 0} k\geq 0

(rangebound by the critical-exponent polynomial, times zero or more optional log {\displaystyle \log } \log s)

... then T ( n ) = Θ ( n c crit log k + 1 ⁡ n ) {\displaystyle T(n)=\Theta \left(n^{c_{\operatorname {crit} }}\log ^{k+1}n\right)} {\displaystyle T(n)=\Theta \left(n^{c_{\operatorname {crit} }}\log ^{k+1}n\right)}

(The bound is the splitting term, where the log is augmented by a single power.)

If b = a 2 {\displaystyle b=a^{2}} {\displaystyle b=a^{2}} and f ( n ) = Θ ( n 1 / 2 ) {\displaystyle f(n)=\Theta (n^{1/2})} {\displaystyle f(n)=\Theta (n^{1/2})}, then T ( n ) = Θ ( n 1 / 2 log ⁡ n ) {\displaystyle T(n)=\Theta (n^{1/2}\log n)} {\displaystyle T(n)=\Theta (n^{1/2}\log n)}.

If b = a 2 {\displaystyle b=a^{2}} {\displaystyle b=a^{2}} and f ( n ) = Θ ( n 1 / 2 log ⁡ n ) {\displaystyle f(n)=\Theta (n^{1/2}\log n)} {\displaystyle f(n)=\Theta (n^{1/2}\log n)}, then T ( n ) = Θ ( n 1 / 2 log 2 ⁡ n ) {\displaystyle T(n)=\Theta (n^{1/2}\log ^{2}n)} {\displaystyle T(n)=\Theta (n^{1/2}\log ^{2}n)}.

3 Work to split/recombine a problem dominates subproblems.

i.e. the recursion tree is root-heavy.

When f ( n ) = Ω ( n c ) {\displaystyle f(n)=\Omega (n^{c})} {\displaystyle f(n)=\Omega (n^{c})}where c > c crit {\displaystyle c>c_{\operatorname {crit} }} {\displaystyle c>c_{\operatorname {crit} }}

(lower-bounded by a greater-exponent polynomial)

... this doesn't necessarily yield anything. If it is furthermore known that
a f ( n b ) ≤ k f ( n ) {\displaystyle af\left({\frac {n}{b}}\right)\leq kf(n)} af\left({\frac {n}{b}}\right)\leq kf(n) for some constant k < 1 {\displaystyle k<1} k<1 and sufficiently large n {\displaystyle n} n (often called the regularity condition)

then the total is dominated by the splitting term f ( n ) {\displaystyle f(n)} f(n):

T ( n ) = Θ ( f ( n ) ) {\displaystyle T\left(n\right)=\Theta \left(f(n)\right)} T\left(n\right)=\Theta \left(f(n)\right)
If b = a 2 {\displaystyle b=a^{2}} {\displaystyle b=a^{2}} and f ( n ) = Ω ( n 1 / 2 + ϵ ) {\displaystyle f(n)=\Omega (n^{1/2+\epsilon })} {\displaystyle f(n)=\Omega (n^{1/2+\epsilon })} and the regularity condition holds, then T ( n ) = Θ ( f ( n ) ) {\displaystyle T(n)=\Theta (f(n))} {\displaystyle T(n)=\Theta (f(n))}.

A useful extension of Case 2 handles all values of k {\displaystyle k} k:

Case Condition on f ( n ) {\displaystyle f(n)} f(n) in relation to c crit {\displaystyle c_{\operatorname {crit} }} {\displaystyle c_{\operatorname {crit} }}, i.e. log b ⁡ a {\displaystyle \log _{b}a} {\displaystyle \log _{b}a} Master Theorem bound Notational examples
2a When f ( n ) = Θ ( n c crit log k ⁡ n ) {\displaystyle f(n)=\Theta (n^{c_{\operatorname {crit} }}\log ^{k}n)} {\displaystyle f(n)=\Theta (n^{c_{\operatorname {crit} }}\log ^{k}n)} for any k > − 1 {\displaystyle k>-1} {\displaystyle k>-1} ... then T ( n ) = Θ ( n c crit log k + 1 ⁡ n ) {\displaystyle T(n)=\Theta \left(n^{c_{\operatorname {crit} }}\log ^{k+1}n\right)} {\displaystyle T(n)=\Theta \left(n^{c_{\operatorname {crit} }}\log ^{k+1}n\right)}

(The bound is the splitting term, where the log is augmented by a single power.)

If b = a 2 {\displaystyle b=a^{2}} {\displaystyle b=a^{2}} and f ( n ) = Θ ( n 1 / 2 / log 1 / 2 ⁡ n ) {\displaystyle f(n)=\Theta (n^{1/2}/\log ^{1/2}n)} {\displaystyle f(n)=\Theta (n^{1/2}/\log ^{1/2}n)}, then T ( n ) = Θ ( n 1 / 2 log 1 / 2 ⁡ n ) {\displaystyle T(n)=\Theta (n^{1/2}\log ^{1/2}n)} {\displaystyle T(n)=\Theta (n^{1/2}\log ^{1/2}n)}.
2b When f ( n ) = Θ ( n c crit log k ⁡ n ) {\displaystyle f(n)=\Theta (n^{c_{\operatorname {crit} }}\log ^{k}n)} {\displaystyle f(n)=\Theta (n^{c_{\operatorname {crit} }}\log ^{k}n)} for k = − 1 {\displaystyle k=-1} k = -1 ... then T ( n ) = Θ ( n c crit log ⁡ log ⁡ n ) {\displaystyle T(n)=\Theta \left(n^{c_{\operatorname {crit} }}\log \log n\right)} {\displaystyle T(n)=\Theta \left(n^{c_{\operatorname {crit} }}\log \log n\right)}

(The bound is the splitting term, where the log reciprocal is replaced by an iterated log.)

If b = a 2 {\displaystyle b=a^{2}} {\displaystyle b=a^{2}} and f ( n ) = Θ ( n 1 / 2 / log ⁡ n ) {\displaystyle f(n)=\Theta (n^{1/2}/\log n)} {\displaystyle f(n)=\Theta (n^{1/2}/\log n)}, then T ( n ) = Θ ( n 1 / 2 log ⁡ log ⁡ n ) {\displaystyle T(n)=\Theta (n^{1/2}\log \log n)} {\displaystyle T(n)=\Theta (n^{1/2}\log \log n)}.
2c When f ( n ) = Θ ( n c crit log k ⁡ n ) {\displaystyle f(n)=\Theta (n^{c_{\operatorname {crit} }}\log ^{k}n)} {\displaystyle f(n)=\Theta (n^{c_{\operatorname {crit} }}\log ^{k}n)} for any k < − 1 {\displaystyle k<-1} {\displaystyle k<-1} ... then T ( n ) = Θ ( n c crit ) {\displaystyle T(n)=\Theta \left(n^{c_{\operatorname {crit} }}\right)} {\displaystyle T(n)=\Theta \left(n^{c_{\operatorname {crit} }}\right)}

(The bound is the splitting term, where the log disappears.)

If b = a 2 {\displaystyle b=a^{2}} {\displaystyle b=a^{2}} and f ( n ) = Θ ( n 1 / 2 / log 2 ⁡ n ) {\displaystyle f(n)=\Theta (n^{1/2}/\log ^{2}n)} {\displaystyle f(n)=\Theta (n^{1/2}/\log ^{2}n)}, then T ( n ) = Θ ( n 1 / 2 ) {\displaystyle T(n)=\Theta (n^{1/2})} {\displaystyle T(n)=\Theta (n^{1/2})}.


Examples

Case 1 example

T ( n ) = 8 T ( n 2 ) + 1000 n 2 {\displaystyle T(n)=8T\left({\frac {n}{2}}\right)+1000n^{2}} T(n)=8T\left({\frac {n}{2}}\right)+1000n^{2}

As one can see from the formula above:

a = 8 , b = 2 , f ( n ) = 1000 n 2 {\displaystyle a=8,\,b=2,\,f(n)=1000n^{2}} a=8,\,b=2,\,f(n)=1000n^{2}, so
f ( n ) = O ( n c ) {\displaystyle f(n)=O\left(n^{c}\right)} f(n) = O\left(n^c\right), where c = 2 {\displaystyle c=2} c=2

Next, we see if we satisfy the case 1 condition:

log b ⁡ a = log 2 ⁡ 8 = 3 > c {\displaystyle \log _{b}a=\log _{2}8=3>c} \log _{b}a=\log _{2}8=3>c.

It follows from the first case of the master theorem that

T ( n ) = Θ ( n log b ⁡ a ) = Θ ( n 3 ) {\displaystyle T(n)=\Theta \left(n^{\log _{b}a}\right)=\Theta \left(n^{3}\right)} T(n) = \Theta\left( n^{\log_b a} \right) = \Theta\left( n^{3} \right)

(This result is confirmed by the exact solution of the recurrence relation, which is T ( n ) = 1001 n 3 − 1000 n 2 {\displaystyle T(n)=1001n^{3}-1000n^{2}} T(n)=1001n^{3}-1000n^{2}, assuming T ( 1 ) = 1 {\displaystyle T(1)=1} T(1)=1).

Case 2 example

T ( n ) = 2 T ( n 2 ) + 10 n {\displaystyle T(n)=2T\left({\frac {n}{2}}\right)+10n} T(n)=2T\left({\frac {n}{2}}\right)+10n

As we can see in the formula above the variables get the following values:

a = 2 , b = 2 , c = 1 , f ( n ) = 10 n {\displaystyle a=2,\,b=2,\,c=1,\,f(n)=10n} a=2,\,b=2,\,c=1,\,f(n)=10n
f ( n ) = Θ ( n c log k ⁡ n ) {\displaystyle f(n)=\Theta \left(n^{c}\log ^{k}n\right)} f(n)=\Theta \left(n^{c}\log ^{k}n\right) where c = 1 , k = 0 {\displaystyle c=1,k=0} c=1,k=0

Next, we see if we satisfy the case 2 condition:

log b ⁡ a = log 2 ⁡ 2 = 1 {\displaystyle \log _{b}a=\log _{2}2=1} \log _{b}a=\log _{2}2=1, and therefore, c = log b ⁡ a {\displaystyle c=\log _{b}a} c=\log _{b}a

So it follows from the second case of the master theorem:

T ( n ) = Θ ( n log b ⁡ a log k + 1 ⁡ n ) = Θ ( n 1 log 1 ⁡ n ) = Θ ( n log ⁡ n ) {\displaystyle T(n)=\Theta \left(n^{\log _{b}a}\log ^{k+1}n\right)=\Theta \left(n^{1}\log ^{1}n\right)=\Theta \left(n\log n\right)} T(n)=\Theta \left(n^{\log _{b}a}\log ^{k+1}n\right)=\Theta \left(n^{1}\log ^{1}n\right)=\Theta \left(n\log n\right)

Thus the given recurrence relation T(n) was in Θ(n log n).

(This result is confirmed by the exact solution of the recurrence relation, which is T ( n ) = n + 10 n log 2 ⁡ n {\displaystyle T(n)=n+10n\log _{2}n} T(n)=n+10n\log _{2}n, assuming T ( 1 ) = 1 {\displaystyle T(1)=1} T(1)=1.)

Case 3 example

T ( n ) = 2 T ( n 2 ) + n 2 {\displaystyle T(n)=2T\left({\frac {n}{2}}\right)+n^{2}} T(n)=2T\left({\frac {n}{2}}\right)+n^{2}

As we can see in the formula above the variables get the following values:

a = 2 , b = 2 , f ( n ) = n 2 {\displaystyle a=2,\,b=2,\,f(n)=n^{2}} a=2,\,b=2,\,f(n)=n^{2}
f ( n ) = Ω ( n c ) {\displaystyle f(n)=\Omega \left(n^{c}\right)} f(n)=\Omega \left(n^{c}\right), where c = 2 {\displaystyle c=2} c=2

Next, we see if we satisfy the case 3 condition:

log b ⁡ a = log 2 ⁡ 2 = 1 {\displaystyle \log _{b}a=\log _{2}2=1} \log _{b}a=\log _{2}2=1, and therefore, yes, c > log b ⁡ a {\displaystyle c>\log _{b}a} c>\log _{b}a

The regularity condition also holds:

2 ( n 2 4 ) ≤ k n 2 {\displaystyle 2\left({\frac {n^{2}}{4}}\right)\leq kn^{2}} 2\left({\frac {n^{2}}{4}}\right)\leq kn^{2}, choosing k = 1 / 2 {\displaystyle k=1/2} k=1/2

So it follows from the third case of the master theorem:

T ( n ) = Θ ( f ( n ) ) = Θ ( n 2 ) . {\displaystyle T\left(n\right)=\Theta \left(f(n)\right)=\Theta \left(n^{2}\right).} T\left(n\right)=\Theta \left(f(n)\right)=\Theta \left(n^{2}\right).

Thus the given recurrence relation T(n) was in Θ(n2), that complies with the f (n) of the original formula.

(This result is confirmed by the exact solution of the recurrence relation, which is T ( n ) = 2 n 2 − n {\displaystyle T(n)=2n^{2}-n} T(n)=2n^{2}-n, assuming T ( 1 ) = 1 {\displaystyle T(1)=1} T(1)=1.)

Inadmissible equations

The following equations cannot be solved using the master theorem:

  • T ( n ) = 2 n T ( n 2 ) + n n {\displaystyle T(n)=2^{n}T\left({\frac {n}{2}}\right)+n^{n}} T(n)=2^{n}T\left({\frac {n}{2}}\right)+n^{n}
    a is not a constant; the number of subproblems should be fixed
  • T ( n ) = 2 T ( n 2 ) + n log ⁡ n {\displaystyle T(n)=2T\left({\frac {n}{2}}\right)+{\frac {n}{\log n}}} T(n)=2T\left({\frac {n}{2}}\right)+{\frac {n}{\log n}}
    non-polynomial difference between f(n) and n log b ⁡ a {\displaystyle n^{\log _{b}a}} n^{\log _{b}a} (see below; extended version applies)
  • T ( n ) = 0.5 T ( n 2 ) + n {\displaystyle T(n)=0.5T\left({\frac {n}{2}}\right)+n} T(n)=0.5T\left({\frac {n}{2}}\right)+n
    a < 1 {\displaystyle a<1} {\displaystyle a<1} cannot have less than one sub problem
  • T ( n ) = 64 T ( n 8 ) − n 2 log ⁡ n {\displaystyle T(n)=64T\left({\frac {n}{8}}\right)-n^{2}\log n} T(n)=64T\left({\frac {n}{8}}\right)-n^{2}\log n
    f(n), which is the combination time, is not positive
  • T ( n ) = T ( n 2 ) + n ( 2 − cos ⁡ n ) {\displaystyle T(n)=T\left({\frac {n}{2}}\right)+n(2-\cos n)} T(n)=T\left({\frac {n}{2}}\right)+n(2-\cos n)
    case 3 but regularity violation.

In the second inadmissible example above, the difference between f ( n ) {\displaystyle f(n)} f(n) and n log b ⁡ a {\displaystyle n^{\log _{b}a}} n^{\log _{b}a} can be expressed with the ratio f ( n ) n log b ⁡ a = n / log ⁡ n n log 2 ⁡ 2 = n n log ⁡ n = 1 log ⁡ n {\displaystyle {\frac {f(n)}{n^{\log _{b}a}}}={\frac {n/\log n}{n^{\log _{2}2}}}={\frac {n}{n\log n}}={\frac {1}{\log n}}} {\displaystyle {\frac {f(n)}{n^{\log _{b}a}}}={\frac {n/\log n}{n^{\log _{2}2}}}={\frac {n}{n\log n}}={\frac {1}{\log n}}}. It is clear that 1 log ⁡ n < n ϵ {\displaystyle {\frac {1}{\log n}}<n^{\epsilon }} {\frac {1}{\log n}}<n^{\epsilon } for any constant ϵ > 0 {\displaystyle \epsilon >0} \epsilon >0. Therefore, the difference is not polynomial and the basic form of the Master Theorem does not apply. The extended form (case 2b) does apply, giving the solution T ( n ) = Θ ( n log ⁡ log ⁡ n ) {\displaystyle T(n)=\Theta (n\log \log n)} {\displaystyle T(n)=\Theta (n\log \log n)}.

Application to common algorithms

Algorithm Recurrence relationship Run time Comment
Binary search T ( n ) = T ( n 2 ) + O ( 1 ) {\displaystyle T(n)=T\left({\frac {n}{2}}\right)+O(1)} T(n)=T\left({\frac {n}{2}}\right)+O(1) O ( log ⁡ n ) {\displaystyle O(\log n)} O(\log n) Apply Master theorem case c = log b ⁡ a {\displaystyle c=\log _{b}a} c=\log _{b}a, where a = 1 , b = 2 , c = 0 , k = 0 {\displaystyle a=1,b=2,c=0,k=0} a=1,b=2,c=0,k=0[5]
Binary tree traversal T ( n ) = 2 T ( n 2 ) + O ( 1 ) {\displaystyle T(n)=2T\left({\frac {n}{2}}\right)+O(1)} T(n)=2T\left({\frac {n}{2}}\right)+O(1) O ( n ) {\displaystyle O(n)} O(n) Apply Master theorem case c < log b ⁡ a {\displaystyle c<\log _{b}a} c<\log _{b}a where a = 2 , b = 2 , c = 0 {\displaystyle a=2,b=2,c=0} a=2,b=2,c=0[5]
Optimal sorted matrix search T ( n ) = 2 T ( n 2 ) + O ( log ⁡ n ) {\displaystyle T(n)=2T\left({\frac {n}{2}}\right)+O(\log n)} T(n)=2T\left({\frac {n}{2}}\right)+O(\log n) O ( n ) {\displaystyle O(n)} O(n) Apply the Akra–Bazzi theorem for p = 1 {\displaystyle p=1} p=1 and g ( u ) = log ⁡ ( u ) {\displaystyle g(u)=\log(u)} g(u)=\log(u) to get Θ ( 2 n − log ⁡ n ) {\displaystyle \Theta (2n-\log n)} \Theta (2n-\log n)
Merge sort T ( n ) = 2 T ( n 2 ) + O ( n ) {\displaystyle T(n)=2T\left({\frac {n}{2}}\right)+O(n)} T(n)=2T\left({\frac {n}{2}}\right)+O(n) O ( n log ⁡ n ) {\displaystyle O(n\log n)} O(n\log n) Apply Master theorem case c = log b ⁡ a {\displaystyle c=\log _{b}a} c=\log _{b}a, where a = 2 , b = 2 , c = 1 , k = 0 {\displaystyle a=2,b=2,c=1,k=0} a=2,b=2,c=1,k=0

See also

Notes

  1. Jump up ^ Bentley, Jon Louis; Haken, Dorothea; Saxe, James B. (September 1980), "A general method for solving divide-and-conquer recurrences", ACM SIGACT News, 12 (3): 36–44, doi:10.1145/1008861.1008865
  2. Jump up ^ Duke University, "Big-Oh for Recursive Functions: Recurrence Relations", http://www.cs.duke.edu/~ola/ap/recurrence.html
  3. Jump up ^ Chee Yap, A real elementary approach to the master recurrence and generalizations, Proceedings of the 8th annual conference on Theory and applications of models of computation (TAMC'11), pages 14–26, 2011. Online copy.
  4. Jump up ^ Massachusetts Institute of Technology (MIT), "Master Theorem: Practice Problems and Solutions", http://www.csail.mit.edu/~thies/6.046-web/master.pdf
  5. ^ Jump up to: a b Dartmouth College, http://www.math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf

References

External Links[edit]

Comments