Why is it okay to do this?

156 Views Asked by At

I am studying asymptotic recurrences for algorithms, and the book says:

$$T(n) = 2T(n/2) + \Theta (n)$$

is technically

$$T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + \Theta (n)$$

for an algorithm (e.g. Mergesort). However apparently it's okay to analyze the running time using the first recurrence. Why is it okay to approximate the second recurrence with the first one?

1

There are 1 best solutions below

2
On

You are interested in the asymptotic behaviour; you can show that any $T$ satisfying the second relation is monotone (increasing), and then you can use the "sandwiching" theorem to relate solutions to the second to solutions to the first —up to some term which will, in hindsight (once you have the solution to the first relation) prove to be negligible.