Search code examples
mathproofmaster-theorem

issues in the proof of master theorem

I am reading the book CLRS(Introduction To Alglorithms , 3rd edition) , and find there seems to be a error in the proof of master theorem . In page 104 , in order to extend the proof to all integer, it use one inequation which seems to be incorrect. On the book it said that:

Our first goal is to determine the depth k such that nk is a constant. Using the inequality [x]<=x+1, we obtain

[x] here means the ceiling of x , it is obvious that [x] < x+1 , not [x] <= x+1 . Besides , in page 54 , there is another inequality confirm what I think

x -1 <  flooring(x) <= x <= ceiling(x) < x+1

Anyone can help to clarify this , why they are conflict ? if this inequality is incorrect then whole the proof won't be correct

Solution

  • Split to two cases:

    1. [x] > x ---> [x] < x+1 (trivial, and I think you agree with it)
    2. [x] = x ---> [x]+1 = x + 1 ---> [x] < x+1

    Similarly for x-1 < floor(x), split to two cases:

    1. floor(x) < x ---> floor(x) > x-1
    2. floor(x) = x ---> floor(x) - 1 = x - 1 ---> floor(x) > x-1

    So, in the last equation - all is left is floor(x)<=c<=ceil(x) - which is pretty much directly from their definition, and from the above two claims we get that:

    x -1 <  flooring(x) <= x <= ceiling(x) < x+1