6
$\begingroup$

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

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

enter image description here

Here (pg.2, exercise 4.1–1) is an example where ceiling is ignored:

enter image description here

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.

  • 0
    "bounding from above" $\neq$ "ignoring. I assume that in the second case, the author implicitly switches from $c$ to some c' > c (which certainly works), as establishing the existence of *some* such constant is likely the goal there. Not saying writing it like this is good (it's *horrible*).2012-04-09

0 Answers 0