How to find the order of a recurrence relation 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!
 A: 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)}$.
A: Perhaps it's the complexity in the sense of big O notation?
In your example,
$T(n) = 3T(n/2)+n$
$T(n) = 3(3T(n/2^2)+n/2)+n = 3^2T(n/2^2) + (3/2)n + n$
$T(n) = 3^2(3T(n/2^3) + n/2^2) + (3/2)n + n = 3^3T(n/2^3) + (3/2)^2n + (3/2)^1 +n$
After $k=\text{floor}(\log_2 n)$ times, you get
$T(n)
=3^{k+1} T(O(1))+ n\sum_{i=0}^k({3\over2})^i
=3^{k+1} T(O(1))+ n\sum_{i=0}^k({3\over2})^i
=3^{k+1} T(O(1)) +n\frac{1.5^{k+1}-1}{1.5-1}$
So that $T(n)=\Theta(n 3^k)= \Theta(n 3^{\text{floor}(\log_2 n)})$.
