Solving a simple recurrence

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.

-

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

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.

-

– Raphael♦ Jan 31 at 9:36
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 7, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9707321524620056, "perplexity_flag": "middle"}