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} $$

Your second analysis basically does the same thing, just using variable substitution instead.

  • $\begingroup$ 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... $\endgroup$ – oldselflearner1959 Apr 9 '18 at 1:22
  • $\begingroup$ @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)$). $\endgroup$ – Luke Mathieson Apr 10 '18 at 0:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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