For fixed , and , a version of the Master theorem states that, with bounded positive base costs,Usual floors and ceilings preserve these bounds when a sufficiently large constant-size base case ensures strict size decrease.
- : , hence , with exponent approximately . Base cases must include because the ceiling otherwise need not decrease.
- : , hence by comparison with the equality recurrence having overhead. If that overhead is actually quadratic this is also tight; the stated upper bound alone does not establish a matching lower bound.
- : , whose expansion is a geometric series, hence , in fact for nonzero base costs. The divide-by-a-constant Master theorem does not apply to a decrement by one.
is asymptotically fastest; is slowest. Even the quadratic-logarithmic upper bound for is smaller than the tight polynomial order of .
Articles by others on the same topic
There are currently no matching articles.