When do floors and ceilings matter while solving recurrences?

Question

I came across places where floors and ceilings are neglected while solving recurrences.

Example from CLRS (chapter 4, pg.83) where floor is neglected:

Here (pg.2, exercise 4.1–1) is an example where ceiling is ignored: (EDIT: I gather from public opinion that this is somewhat fishy.)

In fact in CLRS (pg.88) its mentioned that:

"Floors and ceilings USUALLY do not matter when solving recurrences"

My questions:

1. Here does "usually" means ALL cases ? If yes, i can just forget them all the time.
2. If not, then when do floors and ceilings really count while solving recurrences ?

Note: This ain't a homework problem. I thought about it while I was refreshing my DS and algo concepts.

Answer 1

The floor and ceiling functions satisfy the following inequalities for all x:

• x−1 < ⌊x⌋ ≤ x

• x ≤ ⌈x⌉ < x+1

Thus, in the first example, we have ⌊n / 2⌋ ≤ n / 2. Also, since the logarithm is a monotone increasing function, we know that lg ⌊n / 2⌋ ≤ lg(n / 2). Putting these together, we get the first inequality 2(c ⌊n / 2⌋ lg ⌊n / 2⌋) + n ≤ cn lg(n / 2) + n.

The second example actually contains an error: c lg ⌈n / 2⌉ + 1 is never less than but can be equal to c lg(n / 2) + 1. However, it is true that c lg ⌈n / 2⌉ + 1 ≤ c lg(n / 2 + 1) + 1, which we can then bound from above by, say, c lg(n / 2) + 2 (assuming that n ≥ 2) and thus derive the desired conclusion that T(n) &in; O(lg n).

In fact, the second example contains other errors too: even with the assumptions stated in the following paragraph (which you did not quote), the last = sign should be ≤.

(Ps. Phew, this was a real pain to type without LaTeX. That, if nothing else, is why questions like these are better asked on math.SE.)

Answer 2

Both of your examples are amenable to analysis by the Master Theorem. The Akra–Bazzi theorem generalizes the Master Theorem and gives a sufficient condition for when small perturbations can be ignored (the perturbation h(x) is O(x/log² x)). For integer-indexed recurrences analyzable by Akra–Bazzi, you can ignore the floor and ceiling always, since their perturbations are at most 1.

Every recurrence not covered by Akra–Bazzi is quite exotic in the context of algorithms and data structures.