Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.