You're replying to a comment by Jason Yeo.

February 27, 2012, 02:39

Hi nour,

There are two steps to the method.
1. Guess the solution
2. Prove the solution by induction

For example, we try to get the upper bound of T(n) = T(n/2) + 1 (this is the recurrence relation for binary search)

My guess is o(lgn) so our guess should look like T(n) <= clgn for some c and n > N.

Then we prove the guess by induction.

We assume that T(k) <= clgk holds for k < n.
So,
T(n) = T(n/2) + 1
<= clg(n/2) + 1 (note: we invoke the assumption here)
= clgn - clg2 + 1
= clgn - (clg2 - 1) (note: we rearrange them to the form desired - residual)
<= clgn when c >= 1/(lg2)

done!

Reply To This Comment

(why do I need your e-mail?)

(Your twitter handle, if you have one.)

Type the word "rocket_84": (just to make sure you're a human)

Please preview the comment before submitting to make sure it's OK.