1
$\begingroup$

When we solve the recursive functions using substitution method, the impact of ceil and floor functions is trivial when the size of the input is large enough. For example the answer of $$ T(n) = T(\lceil n/3 \rceil) + O(n) $$ is equivalent to $$ T(n) = T(n/3) + O(n) $$ when the $n$ is large enough. Since $$ T(n) = T(\lceil n/3 \rceil) + O(n) \leq T((n/3) + 1) + O(n) $$ and the size $1$ added to $n/3$ doesn't effect the running time of the algorithm.

My question is, when the ceil and floor functions don't effect the asymptotic bounds of a algorithm, why not to ignore them and simply solve the $T(n)$ without them?

CLRS page 67 edition3 says

When we state and solve recurrences, we often omit floors, ceilings, and boundary conditions.

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ 1) The recurrence you setup up is wrong without the floors and ceils. 2) You need good reasons to simplify a recurrence before solving it, i.e. you need to prove that the simplification doesn't change the $\Theta$-class of the result. (You can't drop all rounding functions!) This is often glossed over in the literature. $\endgroup$ – Raphael♦ Apr 24 '17 at 5:21
  • $\begingroup$ @Raphael the recurrence of merge sort is $T(n) = T(\lfloor n/2 \rfloor) + T(lceil n/2 rceil) + \Theta(n)$ but CLRS solves it as $T(n) = 2T(n/2) + \Theta(n)$. you need to prove that the simplification doesn't change the $\Theta(n)$. I have never seen such proof in any literature !!! $\endgroup$ – M a m a D Apr 24 '17 at 5:57
  • $\begingroup$ I think CLRS do prove this rigorously; check out the proof of the Master theorem. (There is another part for which I am not convinced their proof is airtight.) $\endgroup$ – Raphael♦ Apr 24 '17 at 6:57
  • $\begingroup$ @Drupalist See Section 4.6.2 of CLRS (3rd edition). $\endgroup$ – hengxin Apr 24 '17 at 8:44
  • 1
    $\begingroup$ See cs.stackexchange.com/q/61260/755, cs.stackexchange.com/q/52298/755, and cs.stackexchange.com/q/9569/755. $\endgroup$ – D.W.♦ Apr 24 '17 at 12:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.