Proof of Induction || Iteration method
Hi, I am working on a discrete math problem, and I can't figure out what to do with:
T(n) = 3 + T(n/2), T(0) = 0
I have tried Plug and Chug method and Induction method, but I can't seem to work it out.
My problem is when I try to make a general formula:
T(n) = 3 + T(n/2) => T(n/2) => 3 + T(n^2/2^2)
T(n) = 3 + (3 + T(n^2/2^2))
T(n) = 3 + 3 + T(n^2/2^2) => 3 + T(n^3/2^3)
T(n) = 3 + 3 + (3 + T(n^3/2^3))
T(n) = 3 + 3 + 3 + T(n^3/2^3)
So, g(i) = 3i + T(n^i/2^i)
Since, T(0) = 0. I need to make n^i/2^i equal to 0.
n^i/2^i = 0
and I'm stuck. I've looked at the answer key, and the answer is:
T(n) = 3(⌊log2(n)⌋ + 1)
Can anyone point me to the right direction?
Edit
I've tried this on Wolfram but Wolfram couldn't solve it either.
What I really want to ask is how to deal with iteration substitution method (chug and plug method) when the base case is T(0) = 0, or T(0) = 2. Because, like the example above, when I try to make a general formula, where I would need to make n^i/2^i = 0, I couldn't get anything out of it.