Master theorem: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 6: Line 6:
where we interpret ''n''/''b'' to mean either ⌊''n''/''b''⌋ or ⌈''n''/''b''⌉. Then ''T''(''n'') can be bounded asymptotically as follows.
where we interpret ''n''/''b'' to mean either ⌊''n''/''b''⌋ or ⌈''n''/''b''⌉. Then ''T''(''n'') can be bounded asymptotically as follows.


1. If  ''f''(''n'') = ''O''(''n<sup>logba - &epsilon;</sup>)  for some constant &epsilon; > 0, then ''T''(''n'') = &Theta;(n^<sup>log</sup>). <p>
1. If  ''f''(''n'') = ''O''(''n<sup>logba - &epsilon;</sup>)  for some constant &epsilon; > 0, then ''T''(''n'') = &Theta;(n^<sup>log</sup>). <br>
2. If ''f''(''n'') = &Theta;(''n''<sup>log b a</sup>), then ''T''(''n'') = &Theta;(n<sup>log b a</sup> lg n). <p>
2. If ''f''(''n'') = &Theta;(''n''<sup>log b a</sup>), then ''T''(''n'') = &Theta;(n<sup>log b a</sup> lg n). <br>
3. If ''f''(''n'') = &Omega;(n<sup>log b a + &epsilon;</sup>) for some constant &epsilon; > 0, and if ''af''(''n/b'') &le; ''cf''(''n'') for some constant ''c'' < 1 and all sufficiently large ''n'', then ''T''(''n'') = &Omega;(''f''(''n'')).
3. If ''f''(''n'') = &Omega;(n<sup>log b a + &epsilon;</sup>) for some constant &epsilon; > 0, and if ''af''(''n/b'') &le; ''cf''(''n'') for some constant ''c'' < 1 and all sufficiently large ''n'', then ''T''(''n'') = &Omega;(''f''(''n'')).

Revision as of 20:17, 25 September 2014

MASTER THEOREM

Let a ≥ 1 and b > 1 be constants, let f(n) be a function, and let T(n) be defined on the nonnegative integers by the recurrence

T(n) = aT(n/b) + f(n),

where we interpret n/b to mean either ⌊n/b⌋ or ⌈n/b⌉. Then T(n) can be bounded asymptotically as follows.

1. If f(n) = O(nlogba - ε) for some constant ε > 0, then T(n) = Θ(n^log).
2. If f(n) = Θ(nlog b a), then T(n) = Θ(nlog b a lg n).
3. If f(n) = Ω(nlog b a + ε) for some constant ε > 0, and if af(n/b) ≤ cf(n) for some constant c < 1 and all sufficiently large n, then T(n) = Ω(f(n)).