# 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.

-
A lot of Master theorem type recurrences can be solved exactly. While this computes more information than what is required for the asymptotics I believe it does add to the understanding of what exactly is going on with these recurrences. There is one example here and another one here and here. –  Marko Riedel Jan 21 '13 at 22:28
@MarkoRiedel That's actually exactly what I needed -- the Master Theorem. I was able to get the information I needed with a simple Google search for it. Thanks! –  Benjamin Kovach Jan 21 '13 at 22:47

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)}$.

-

Perhaps it's the complexity in the sense of big O notation?

$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)})$.

-