You're viewing a comment by nour and its responses.

nour Permalink
February 19, 2012, 06:33

I am from syria ,I speak arabic , I watch lecture 1&2 ,I did not understand "substitution method" ,can you explain it in simple way ,with more examples. thank you.

Comment Responses

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.
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)


Reply To This Comment

(why do I need your e-mail?)

(Your twitter handle, if you have one.)

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

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