Master theorem: Difference between revisions
Jump to navigation
Jump to search
| Line 2: | Line 2: | ||
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 | 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''), | ''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. | 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 - ε</sup>) for some constant ε > 0, then ''T''(''n'') = Θ(n^<sup>log</sup>). <br> | 1. If ''f'' (''n'') = ''O''(''n<sup>logba - ε</sup>) for some constant ε > 0, then ''T''(''n'') = Θ(n^<sup>log</sup>). <br> | ||
2. If ''f''(''n'') = Θ(''n''<sup>log b a</sup>), then ''T''(''n'') = Θ(n<sup>log b a</sup> lg n). <br> | 2. If ''f'' (''n'') = Θ(''n''<sup>log b a</sup>), then ''T''(''n'') = Θ(n<sup>log b a</sup> lg n). <br> | ||
3. If ''f''(''n'') = Ω(n<sup>log b a + ε</sup>) 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'')). | 3. If ''f'' (''n'') = Ω(n<sup>log b a + ε</sup>) 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'')). | ||
Revision as of 20:18, 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)).