Floors And Ceilings
Floors and ceilings: To complete the proof of the master theorem, we must now extend our analysis to the situation in which floors and ceilings are used in the master recurrence, so that the recurrence is defined for all integers, not just exact powers of b. Obtaining a lower bound on
and an upper bound on
is routine, since the bound ⌈n/b⌉≥ n/b can be pushed through in the first case to yield the desired result, and the bound ⌊n/b⌋≤ n/b can be pushed through in the second case. Lower bounding the recurrence (4.11) requires much the same technique as upper bounding the recurrence (4.10), so we shall present only this latter bound.
We modify the recursion tree of Figure 4.3 to produce the recursion tree in Figure 4.4. As we go down in the recursion tree, we obtain a sequence of recursive invocations on the arguments
Figure 4.4: The recursion tree generated by T(n) = aT(⌈n/b⌉) f(n). The recursive argument nj is given by equation (4.12).
n,
⌈n/b⌉,
⌈⌈n/b⌉/b⌉,
⌈⌈⌈n/b⌉/b⌉/b⌉,
⋮
Let us denote the jth element in the sequence by nj, where
Our first goal is to determine the depth k such that nk is a constant. Using the inequality ⌈x⌉ ≤ x 1, we obtain
