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
    The first example is perfectly valid because $\lfloor n/2 \rfloor \le n/2$. The second example is a little fishy.2012-04-08
  • 2
    [These notes](http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/99-recurrences.pdf) might help; see especially Section 6.2012-04-08
  • 0
    @JeffE : thats good stuff.2012-04-08
  • 1
    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.2012-04-08
  • 1
    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.2012-04-08
  • 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