Showing a recurrence is $\Theta$(n)

Specifically how do you go about showing that $$2T(n/2)+1 =\Theta(n)$$ Not looking for an answer, as much as the process? I'm studying for a test and this is one of the review problems. Thanks in advance

-
In my edit, I removed the "if n>1, 1 if n=1" part, since it's redundant. – Rick Decker Oct 3 '12 at 19:35
Where is the recursion? – Did Oct 3 '12 at 19:49
@did. Heh, I missed that. Too smart for my own good, I suppose. Of course you and I both know that it's likely that the OP meant $T(n)=2T(n/2)+1$ and then is really asking to show that $T(n)=\Theta(n)$ (for some suitable base case). – Rick Decker Oct 3 '12 at 20:02

1 Answer

Have you been introduced to what's often called the Master Theorem? If so, use it; if not, you can argue this way (sometimes known as iterative expansion). Suppose for a moment that $n=2^k$ for some $k>0$. Then, \begin{align} T(2^k) &= 2T(2^{k-1})+1 &\text{now expand the T term}\\ &=2(2T(2^{k-2}+1)+1 = 2^2T(2^{k-2})+2+1 &\text{and again}\\ &=2^2(2T(2^{k-3}+1)+2+1 =2^3T(2^{k-3})+4+2+1 &\text{continue...}\\ & =2^4T(2^{k-4})+8+4+2+1 \end{align} Do you see a pattern? What does the expansion look like when $k-j$ gets driven down to zero, that is, when you've expressed $T(n)$ in terms of $T(1)$?

Since this is tagged as homework, I'll leave some things for you. In particular, the expression you wind up with is just a guess and also it is currently good only for $n$ values which are powers of 2. However, it should be easy enough to prove your guess by induction and that will be all you need. (Well, except that you need to specify some starting value for $T(1)$, like 1, say, to make things pretty.)

Edit: Care and feeding of the Master Theorem Depending on the level of exposition, there are several versions of the creature known as the Master Theorem. I'll give you the simplest version, since it's easily applicable to your problem.

Suppose that $p$ is a positive integer, $q >1$ is real, $d\ge0$ is real and $r>0$ is real and we have a recurrence defined by $$T(n)=\begin{cases} pT(n/q)+n^d&\text{ if }n>1\\ r&\text{ if }n=1\\ \end{cases}$$ then $$T(n)=\begin{cases} \Theta(n^d)&\text{ if }p<q^d\\ \Theta(n^d\log n)&\text{ if }p=q^d\\ \Theta(n^{\log_qp})&\text{ if }p>q^d\\ \end{cases}$$ In your case, $T(n)=2T(n/2)+1$, we have $p=2,q=2,d=0$ and we may take any positive $r$ we wish without changing the result. Now, $q^d=2^0=1$ so $p>q^d$, which places us in the third case, so we conclude that $$T(n)=\Theta(n^{\log_22})=\Theta(n^1)=\Theta(n)$$ which is exactly what you were asked to show.

-
We just started the Master Theorem, can you give an explanation as to how you would use it for this? – Extinct23 Oct 3 '12 at 21:09
Your wish is my command. I'll edit my answer. – Rick Decker Oct 3 '12 at 21:17
Thanks! this is awesome; you're the man! – Extinct23 Oct 3 '12 at 22:12