# Why does this recurrence give O(n) time?

Given this following recurrence: $$T(n) = T(n/2) + O(n)$$Find the final time complexity.

My first thought is $O(n\log n)$, since there is at most $\log n$ times the $O(n)$ will appear.

However, if we adopt the following analysis and let $n=2^m$, then we have:

$$T(2^m) = T(2^{m-1}) + k(2^m) = T(2^{m-2}) + k(2^m + 2^{m-1})...$$

Which we can then condense to have the cost become:

$$2^m + 2^{m-1} .... + 1 = 2^{m+1} - 1$$

And so since the cost is $O(2^m)$, we have our $O(n)$ time as required.

Is the analysis valid? Because I have so very often seen proofs using recurrences of the form $T(n) = T(n/2) + ...$, and they all similarly concluded that there will be $\log n$ times of the relationship.

Which is correct?

Your second analysis is correct, and $T(n) \in \Theta(n)$. You can also use the Master Theorem to verify this.
The reason that the first "naive" analysis fails is that you don't have $O(n)$ at each step, you have $O(\frac{n}{2^{i}})$ where $i$ is how far down the recursion you've gone.
Ignoring the constant multipliers for the moment, this gives $$\sum_{i=0}^{\log n} \frac{n}{2^{i}} = \frac{\sum_{i=0}^{\log n}n}{\sum_{i=0}^{\log n}2^{i}} = \frac{n\log n}{2^{log n + 1}} = \frac{n\log n}{2 \log n} = \frac{n}{2}$$
• I've checked the master theorem, and it seems mine fits case 1. But given case 1, in this example $a = 1$ and $b=2$, so $\log_b (a) = 0 < c = 2$. which doesn't seem to apply... – oldselflearner1959 Apr 9 '18 at 1:22
• @oldselflearner1959, there's actually a bit of a problem with the statement of the recurrence - using big-oh terms like they're functions is a bit dicey, but in this case, assume that by $O(n)$ it means $k\cdot n$ for some fixed $k$. Then you actually have case 3. $c_{crit} = \log_{b}a = 0$ and $c = 1$, so $T(n) \in \Theta(n)$. If we take the $O(n)$ to mean "some function in the set $O(n)$", then we can get quite different answers (e.g. pick any constant function, you get case 2, and $T(n) \in \Theta(\log n)$). – Luke Mathieson Apr 10 '18 at 0:36