-1
$\begingroup$

This question already has an answer here:

Solve the following recurrence equations

a. T(n) = T(n/2) + 18

b. T(n) = 2T(n/2) + 5n

c. T(n) = 3T(n/2) + 5n

d. T(n) = T(n/2) + 5n

This is only a sample of what I was given but I am not sure what the question is asking me or how to solve it? Can someone please explain this to me?

The only thing I really know about them is that it has something having to do with Big O and such. I was a bit sick when they gave this lecture so I couldn't really grasp the concept. Could someone please help me understand this?

$\endgroup$

marked as duplicate by Juho, Yuval Filmus, D.W., Raphael Nov 11 '13 at 13:50

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1
$\begingroup$

Solving a recurrence essentially means getting rid of the recursion and giving a way to calculate the answer such a recursive function would give you, without doing the recursion. Additionally, when you solve it in terms of asymptotic complexity, then it becomes a bit easier, since you don't care about the slower-growing terms and can get rid of a lot of terms on the way.

So, choosing an example, if we have, $T(n) = T\left(\frac{n}{2}\right) + 18$ then $T(n) = \Theta\left(\log n\right)$. See, I got rid of the recursion; there is no longer any recursion on the right-hand-side. How did I do this? Well, there are two ways.

General way

We recurse a few steps, and generalize it to step $k$: $$ \begin{eqnarray} T(n)&=&T\left(\frac{n}{2}\right) + 18\\ T\left(\frac{n}{2}\right)&=&T\left(\frac{n}{4}\right) + 18\\ T\left(\frac{n}{4}\right)&=&T\left(\frac{n}{8}\right) + 18\\ &...&\\ T\left(\frac{n}{2^k}\right)&=&T\left(\frac{n}{2^{k+1}}\right) + 18\\ T\left(1\right)&=&\Theta(1)&\genfrac{}{}{0}{}{\text{We choose a (constant) base}}{\text{ case, unless given one}}\\ \end{eqnarray} $$

Then we see how large $k$ must be in order to get down to $T(1)=T\left(\frac n n\right)$:

$$ \begin{eqnarray} 2^{\max k}&=&n\\ {\max k} &=& \Theta \left(\log n\right)\\ \end{eqnarray} $$

Now we know it will recurse $\max k$ times, so we replace each $T(x)$ on the right-hand-side with its recursed value (calculated above), then generalize it to $\max k$.

$$ \begin{eqnarray} T(n)&=&T\left(\frac{n}{2}\right) + 18\\ &=&\left(T\left(\frac{n}{4}\right) + 18\right) + 18 & \text{Replace }T\left(\frac{n}{2}\right)\text{ in terms of }T\left(\frac{n}{4}\right)\\ &=&\left(\left(T\left(\frac{n}{8}\right) + 18\right) + 18\right) + 18& ...\\ &...&\\ &=&T\left(\frac{n}{2^{\max k}}\right) + 18\cdot {\max k}\\ &=&T\left(1\right) + 18\cdot \Theta \left(\log n \right)\\ &=&\Theta \left(\log n \right)\\ \end{eqnarray} $$

Master theorem

An easier way for special cases of asymptotic recurrence relations is called the master theorem, and allows you to "cheat" if $T(n)$ follows 3 specific forms, and you want the asymptotic solution. See the master theorem page for the different forms, but I will demonstrate for the example I chose:

General form:

$T(n) = a \; T\!\left(\frac{n}{b}\right) + f(n) \;\;\;\; \mbox{where} \;\; a \geq 1 \mbox{, } b > 1$

So for us, $a=1,b=2,f(n)=18$. Therefore, $\log_b a = 0$ This fits Case 2 as follows:

Case 2:

If:

$f(n) = \Theta\left( n^{c} \log^{k} n \right)$, where $c = \log_b a$, and some $k \ge 0$.

Then:

$T(n) = \Theta\left( n^{c} \log^{k+1} n \right)$

We have $c=\log_b a=0$ and choose $k=0$. This gives us:

$$\begin{eqnarray} f(n) &\stackrel{?}{=}& \Theta\left( n^{c} \log^{k} n \right)\\ &\stackrel{?}{=}& \Theta\left( n^{0} \log^{0} n \right)\\ &\stackrel{?}{=}& \Theta\left( 1 \right)&\checkmark\\ \end{eqnarray}$$

Which is true, so we match the case. Therefore:

$$\begin{eqnarray} T(n) &=& \Theta\left( n^{c} \log^{k+1} n \right)\\ &=& \Theta\left( n^{0} \log^{0+1} n \right)\\ &=& \Theta\left( \log n \right)\\ \end{eqnarray}$$

$\endgroup$
  • $\begingroup$ I like how easy this is for me to follow and for the most part I see where you are going with this my question is for the first way you showed me, how exactly does max k = log n? $\endgroup$ – Marlin Hankin Nov 11 '13 at 2:29
  • $\begingroup$ @MarlinHankin Well, the $2^k$ is on denominator of $T\left(\frac {n}{2^k}\right)$, and we are trying to see how large $k$ must be to get $T(1)=T\left(\frac {n}{n}\right)$; thus we set $2^{\max k}=n$ . Then to solve for $\max k$ you $\log (\cdot)$ both sides, it takes down the $\max k$ from exponent status ($\log 2^{\max k}=\max k\cdot \log 2$), and leaves $\max k\cdot \log 2 = \log n$. Since I decided to switch to $\Theta(\cdot)$ here, I safely disregard the $\log 2$ part. $\endgroup$ – Realz Slaw Nov 11 '13 at 3:05
  • $\begingroup$ You say this is not a duplicate of the reference question, but all you offer as answer has been covered extensively there. Huh? $\endgroup$ – Raphael Nov 11 '13 at 13:51
  • $\begingroup$ @Raphael mmm sorry, I misunderstood that question. $\endgroup$ – Realz Slaw Nov 11 '13 at 14:47
  • $\begingroup$ I thank you for clearing that up for me but what about for something that is like..... T(n) = T(n/5) + T(7n/10) + 3n $\endgroup$ – Marlin Hankin Nov 11 '13 at 16:09

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