Let () be defined recursively as follows: (1) = and () = (⌊n/2⌋) + for all integers ≥ 2, where is an arbitrary positive constant. Prove by induction on that () ≤ log + . (Note: ⌊⌋ is the floor function, defined as rounding down to the closest integer that is ≤ .)
Can anyone help me out step by step with this example? Thanks in advance!
T(1) = and T(n) = T(⌊n/2⌋) +
We need to prove that T(n) <= c * log(2, n) + c
Simplest proof
The T(n) = T(⌊n/2⌋) + recursion will need ⌊log(2, n)⌋ steps to reach T(1) (because we always halve the index, which adds up into a binary logarithm)
Since we add c each time we go further down in the recursion, the ⌊log(2, n)⌋ steps amount to c * ⌊log(2, n)⌋.
So, since we have reached T(1), we have
c * ⌊log(2, n)⌋ + T(1) =
c * ⌊log(2, n)⌋ + c
and it is trivial that
c * ⌊log(2, n)⌋ + c <= c * log(2, n) + c
How to prove this with induction
Since we have a division by 2 each time for the index, it is clear that if ⌊log(2, i)⌋ = ⌊log(2, j)⌋, then T(i) = T(j), because the exact parameter value is not important by itself, it is the number of steps that determines the value we multiply c with.
And, since in our condition above ⌊log(2, i)⌋ = ⌊log(2, j)⌋, the steps needed for T(i) and T(j) are exactly the same, which proves that
if i = 2^p and i < j < 2^(p + 1), then
T(i) = T(j) = c * ⌊log(2, i)⌋ + c and it is true that
c * ⌊log(2, i)⌋ + c <= c * log(2, i) + c < c * log(2, j) + c
Hence, exact equalities occur when we have a power of 2 as a parameter, while, otherwise T(j) is strictly smaller than c * log(2, j) + c
As a result, it is enough to prove that
statement(2^n) => statement(2^(n + 1))
T(2^(n + 1)) =
T(2 ^ n) + c =
c * log(2, 2^n) + c + c =
c * log(2, 2^n) + c * log(2, 2) + c =
c * (log(2, 2^n) + log(2, 2)) + c =
c * (log(2, 2 * 2^n)) + c =
c * (log(2, 2^(n + 1))) which, accordingly to the concept of mathematical inclusion proves our statement.