Master theorem: Difference between revisions
Jump to navigation
Jump to search
(Created page with "== 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''(...") |
|||
| Line 5: | Line 5: | ||
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^(logba - ε)) for some constant ε > 0, then ''T''(''n'') = Θ(n^log) | |||
Revision as of 20:07, 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(n^(logba - ε)) for some constant ε > 0, then T(n) = Θ(n^log)