Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 1 down vote favorite

I'm having a real hard time solving recurrences using the substitution method.

Show that: $T(n) = T(n/2) + 1$ is $O(\lg n)$

I thought this to be relatively easy:

We have to show that $T(n) \leq c \lg n$

Substitution gives me:

$\qquad \begin{align} T(n) &\leq c \lg(n/2) + 1 \\ &= c \lg n - c \lg 2 + 1 \\ &= c \lg n - c + 1 \\ &\leq c \lg n \end{align}$

for every c.

I was under the impression this was it, but when I was looking for an answer, I came around a much more elaborate answer on the web, given involving subtracting a constant. I don't get why that's needed, I thought I had shown what was needed.

Any help would be greatly appreciate, starting Monday I'm enrolled in an algorithms class and I don't want to get behind!

We are using the CLRS book (surprise) and though I appreciate the amount of information in it, I'd rather have some more resources. I've really enjoyed a datastructures class and I really think I can enjoy this as well, but more resources would be very much appreciated.

share|improve this question
1  
We have a reference question with ample material about solving recurrences, in particular this answer. – Raphael♦ Jan 30 at 20:54
Your substitution proves nothing. You use the claim to derive the claim -- that's not very helpful. – Raphael♦ Jan 30 at 20:56
1  
@Raphael This is proof by induction. – Yuval Filmus Jan 31 at 0:27
Your solution looks fine, though you'd better write it as an induction, i.e $T(n) = T(n/2) + 1 \leq c\lg(n/2) + 1$ and so on. You also need to take care of the base case, and notice that you get a condition on $c$ (not all $c$ work). – Yuval Filmus Jan 31 at 0:28
1  
@YuvalFilmus No, it's not. What is written there could be used as the inductive step, true. Given the level of the question, I would not assume that Oxymoron knows what happens there; the question even says "substitution method". – Raphael♦ Jan 31 at 9:34
show 2 more comments

1 Answer

up vote 2 down vote

Luckily i had 2 day ago the algorithm exam and so i was able to solve your question :-) When solving recurrences try first to use the Master method, if you can't succeed than try other methods.

enter image description here

share|improve this answer
1) The asker explicitly asks for how to do the "direct" proof. 2) Please type your solution; you can use LaTeX. – Raphael♦ Jan 31 at 9:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.