# When do ﬂoors and ceilings matter while solving recurrences?

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:

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.

-
The first example is perfectly valid because $\lfloor n/2 \rfloor \le n/2$. The second example is a little fishy. – Rahul Apr 8 '12 at 15:02
These notes might help; see especially Section 6. – JeffE Apr 8 '12 at 16:07
@JeffE : thats good stuff. – Tejas Patil Apr 8 '12 at 16:16
In many situations, it is intuitively clear that whether the floor or ceiling function is there or not doesn't make a significant difference compared to the "main" term. Now one could argue, correctly, that if it is intuitively clear, surely a tight proof cannot be hard. True, but if we are solving a hard problem, filling in petty details can distract from the main point. At the "student" stage, I think one should err in the direction of too much detail. – André Nicolas Apr 8 '12 at 17:29
The second one is incredibly sloppy. Even with the qualification in the original that the last step holds for $c\ge 1$, it should be $\le$, and the second $\le$ is simply false. I certainly wouldn’t accept it as written. – Brian M. Scott Apr 8 '12 at 18:33