I have some homework that I'm working on where there is a whole section of problems I need to solve taking the following form:
"Assume that T(1) = 1, and find the order of function T(n)."
I have no idea what this means, really, and I'm having difficulty finding anything specific enough online. What I've found (I think) is that a function of order k is a function that can be solved using the k previous terms of the sequence.
However, I don't really know how to apply this. An example of what I'm working with is as follows:
$$T(n) = 3T(\frac{n}{2}) + n$$
If someone could walk me through exactly what I need to do to find the order of this function, that would be great; I'm really lost.
Thanks in advance!
Best Answer
We want to find $T(n)$ given the recurrence $$T(n) = 3T(n/2) + n$$ Let us write $n= 2^m$ and call $g(m) = T(2^m)$. We then have \begin{align} g(m) & = 3 g(m-1) + 2^m = 2^m + 3 (2^{m-1} + 3g(m-2)) = 2^m + 3 \cdot 2^{m-1} + 3^2 g(m-2)\\ & = 2^m + 3 \cdot 2^{m-1} + 3^2 \cdot 2^{m-2} + 3^3 g(m-3)\\ & = 2^m + 3 \cdot 2^{m-1} + 3^2 \cdot 2^{m-2} + 3^3 \cdot 2^{m-3} + 3^4 g(m-4) \end{align} Hence, using induction, you can prove that \begin{align} g(m) & = 2^m + \left(\dfrac32\right) \cdot 2^m + \left(\dfrac32\right)^2 \cdot 2^m + \cdots + \left(\dfrac32\right)^{m-1} \cdot 2^m + 3^m g(0)\\ & = 2^m \dfrac{(3/2)^m-1}{3/2-1} + 3^m g(0) = 2 \cdot (3^m-2^m) + 3^m g(0)\\ & = (g(0) + 2) 3^m - 2^{m+1} = (g(0) + 2) 3^{\log_2(n)} - 2n\\ & = (g(0) + 2) n^{\log_2(3)} - 2n\\ \end{align} Hence, $T(n)$ grows as $n^{\log_2(3)}$.