Process of solving recurrence relations

Question

I am having trouble understanding how to solve a recurrence relation. If you can please help walk me through this one:

$T(n) = T(\dfrac{n}{2}) + 5$

Initial conditions $T(0) = 0$ and $T(1) = 1$

My teacher did not explain this very clearly and I'm very confused on where to begin..if someone can please point me in the right direction, don't necessarily need to solve.

From looking at the internet, I believe this relation is non-homogenous because of the $5$, so would the first step be to solve the homogenous equation and then add the $5$?

Answer 1

The problem with your formula is with the $n/2$; in general, to calculate $T(n)$ defined by recurrence (i.e.in terms of (one or more) values of $T(k)$ with $k < n$) you must substitute into the formula for $T(n)$ the formula for $T(n-1)$, and so on, until you reach (after a finite number of steps) the "base" case, i.e. $T(1)$ or $T(0)$.

In your problem, starting for example with $T(5)$, we need $T(5/2)$, but in this way we cannot reach $T(1)$ or $T(0)$.

The problem is easy if we may assume - as suggested by @lhf - that $n$ is a power of $2$.

In this case $T(4) = T(2) + 5 =(T(1) + 5) +5 = (1 + 5) + 5 = 11$, and so on : $T(8) = T(4) + 5 = 16$ ...

I suppose that your question is an application of the Master theorem.

We are in the Case 2 : where $f(n) = 5 = \Theta (n^c log^k n)$, with $c=0$ and $k=0$.

From : $T(n) =T(n/2)+5$, we have $a=1$ and $b=2$, so that $\log_2 1 = 0$ and $c = 0 = log_2 1$.

It follows that $T(n) = \Theta(f(n)) = \Theta(n^clog^{k+1} n) = \Theta(log(n))$.

Answer 2

This suffers from the common problem that $T(x)$ is not defined when $x$ is not a positive integer although the recursion needs such values.

Additionally, any initial condition involving $T(0)$ is suicidal since, for $n=0$, the identity defining $T$ reads $T(0)=T(0)+5$.

To get a well-defined problem, consider $S(k)=T(2^k)$ for every $k\geqslant0$, then $S(k)=S(k-1)+5$. This implies that $$S(k)-5k=S(k-1)-5(k-1), $$ thus $S(k)=5k+S(0)$, which means that $T(2^k)=5k+T(1)$. Likewise, for every odd integer $i$, $T(2^ki)=5k+T(i)$. Thus, the initial conditions needed to get a well defined sequence $T$ are all the $T(2i+1)$.

Seeing that $T(2^k)=5k+T(1)$, what you are asked to say is probably that $T(n)$ is of the order of a multiple of $\log n$.

Take-home message: If $x_n=x_{n-1}+b$, the sequence $y_n=x_n-bn$ is such that $y_n=y_{n-1}$ for every $n$, hence $y_n=y_0$, that is, $x_n=bn+x_0$. Likewise, if $x_n=ax_{n-1}+b$ with $a\ne1$, the sequence $y_n=x_n+b/(a-1)$ is such that $y_n=ay_{n-1}$ for every $n$, hence $y_n=a^ny_0$, that is, $x_n=a^n(x_0+b/(a-1))-b/(a-1)$.