Help solve recurrence : f(x) = 2f(x-1) + x

Question

While trying to analyze the time complexity of the heapify algorithm , I came up with the following recurrence for it's time complexity in terms of heap height:

T(h) = 2T(h-1) + h 

Could you help me approach this recurrence?

Answer 1

To solve the recurrence $$a_h=2a_{h-1}+h \tag{1}$$ write $$b_h=a_h+h$$ Adding $h$ to both sides of $(1)$ gives $$b_h=2b_{h-1}+2$$ Can you take it from here?

Answer 2

$T(h)=2T(h-1)+h=2(2T(h-2)+(h-1))+h=2^2(2T(h-3)+(h-2))+2(h-1)+h$ . . . so you get: $$T(h)= \Sigma_{i=0}^h2^i*(h-i)$$

Answer 3

For another solution, suppose $f(x)=ax+b$. If $f(x)=2f(x-1)+x$, then $$ax+b=2a(x-1)+2b+x=(2a+1)x+2b-2a$$ and so $$(a+1)x=b+2a.$$ The above gives $0=b+2a$. For an initial value $f(0)=x_0$, $f(0)=b=x_0$. Thus $f(x)=x_0-\frac{x_0}{2}x$.

I guess the first line might be sort of unsatisfying, but it is pretty reasonable to guess that such an $f$ could be linear, and if that didn't work, some other polynomial. The problem of finding all such functions $f$ is a different question, though, so I think it suffices to find just one.

Answer 4

$$a_k = 2a_{k-1} + k$$ $$\implies \dfrac{a_k}{2^k} = \dfrac{a_{k-1}}{2^{k-1}} + \dfrac{k}{2^k}$$

$$\implies \dfrac{a_k}{2^k} - \dfrac{a_{k-1}}{2^{k-1}} = \dfrac{k}{2^k}$$

$$\implies \sum_{k=1}^{n} \left(\dfrac{a_k}{2^k} - \dfrac{a_{k-1}}{2^{k-1}}\right) = \sum_{k=1}^{n} \dfrac{k}{2^k}$$

$$ \implies \dfrac{a_n}{2^n} - \dfrac{a_0}{2^0} = \sum_{k=1}^{n} \dfrac{k}{2^k} $$

Note that the R.H.S. is an Arithmetic-Geometric Progression. Thus,

$$\sum_{k=1}^{n} \dfrac{k}{2^k} = \dfrac{1}{2^n}(2^{n+1} - n -2)$$

$$\implies \dfrac{a_n}{2^n} - \dfrac{a_0}{2^0}= \dfrac{1}{2^n}(2^{n+1} - n -2) $$

$$ \displaystyle \implies \boxed{a_n = 2^n(a_0 + 2) - n -2} $$

Answer 5

You can write it as a matrix equation: $$\begin{pmatrix}1\\ T_h\end{pmatrix}=\begin{pmatrix}1&0\\ h&2\end{pmatrix}{1\choose T_{h-1}}=\begin{pmatrix}1&0\\ h&2\end{pmatrix}\begin{pmatrix}1&0\\ h-1&2\end{pmatrix}{1\choose T_{h-2}}=\\ \begin{pmatrix}1&0\\ (1+2)h-2&2^2\end{pmatrix}\begin{pmatrix}1&0\\ h-2&2\end{pmatrix}{1\choose T_{h-3}}=\\ \begin{pmatrix}1&0\\ (1+2+2^2)h-(2+2\cdot 2^2)&2^3\end{pmatrix}\begin{pmatrix}1&0\\ h-3&2\end{pmatrix}{1\choose T_{h-4}}=\cdots=\\ \begin{pmatrix}1&0\\ (1+2+\cdots+2^{h-1})h-(2+2\cdot 2^2+\cdots+(h-1)\cdot 2^{h-1}&2^h\end{pmatrix}{1\choose T_0}=\\ \begin{pmatrix}1&0\\ (2^h-1)h-(2^hh-2^{h+1}+2)&2^h\end{pmatrix}{1\choose T_0}=\\ \begin{pmatrix}1&0\\ 2^{h+1}-h-2&2^h\end{pmatrix}{1\choose T_0}=\\{1\choose 2^{h+1}-h-2+2^hT_0}.$$