Maple can find closed-form solutions for recurrence relations. You may recall the recurrence relation for the Fibonacci sequence: $F(n) = F(n - 1) + F(n - 2)$ where $F(0) = F(1) = 1$. In Maple, we can solve this with the rsolve(...) function. The first argument is a set containing the recurrence relation and the initial conditions, and the second is a set of those functions being solved for:
[> rsolve( {F(n) = F(n - 1) + F(n - 2), F(0) = 1, F(1) = 1}, {F(n)} );
$\left\{ F \left( n \right) = \left( 1/2+1/10\,\sqrt {5} \right) \left( 1/2\,\sqrt {5}+1/2 \right) ^{n}+ \left( 1/2-1/10\,\sqrt {5} \right) \left( -1/2\,\sqrt {5}+1/2 \right) ^{n} \right\}$
This looks awkward, but we can evaluate this to floating-point numbers:
[> evalf( % );
$\left\{ F \left( n \right) = 0.7236067977\,{ 1.618033988}^{n}+ 0.2763932023\, \left( - 0.6180339880 \right) ^{n} \right\}$
You'll note that the first term is $1.6180^n$ and the second is $(-0.6180)^n$. As $n \rightarrow \infty$, the second term goes to zero, and thus the asymptotic behavior is $\textrm{O}\left( \left( 1/2\,\sqrt {5}+1/2 \right) ^{n} \right)$.
You will solve recurrence relations in terms of both run times and memory use of algorithms.
Consider, for example, a binary search: $F(n) = F\left(\frac{n}{2}\right) + 1$, so we ask:
[> rsolve( {F(n) = F(n/2) + 1, F(1) = 1}, {F(n)} );
$\left\{ F(n) = \frac{\ln(n)}{\ln(2)} + 1\right \}$
From this, you note that the run time is $\textrm{O}\left(\log_2(n)\right)$.
For Karatsuba's algorithm for multiplying two integers of $n$ digits, this gets transformed into smaller problems of multiplying three pairs of integers of $\frac{n}{2}$ digits, followed by a few summations, so the run time is:
[> rsolve( {F(n) = 3*F(n/2) + n, F(1) = 1}, {F(n)} );
$\left\{ F \left( n \right) =3\,{n}^{{\frac {\ln \left( 3 \right) }{ \ln \left( 2 \right) }}}-2\,n \right\}$
From this, we see the run time is $\textrm{O}\left(n^{\log_2(3)}\right)$.
For Strassen's algorithm for multiplying two $n \times n$ matrices, this gets transformed into seven problems of multiplying pairs of $\frac{n}{2} \times \frac{n}{2}$ matrices, followed by a few matrix-matrix summations, so the run time is:
[> rsolve( {F(n) = 7*F(n/2) + n^2, F(1) = 1}, {F(n)} );
$\left\{ F \left( n \right) =7/3\,{n}^{{\frac {\ln \left( 7 \right) }{\ln \left( 2 \right) }}}-4/3\,{n}^{2} \right\}$
From this, we see the run time is $\textrm{O}\left(n^{\log_2(7)}\right)$.
Both of these algorithms transform into solving two problems of half the size, with linear algorithms required to either split the problem into the two sub-problems, combine the two sub-solutions into a total solution, or both:
[> rsolve( {F(n) = 2*F(n/2) + n, F(1) = 1}, {F(n)} );
$\left\{ F \left( n \right) =n+{\frac {\ln \left( n \right) n}{\ln \left( 2 \right) }} \right\}$
Again, this supports what we know: the run time is $\textrm{O}\left(n \log_2(n)\right)$.
For example, suppose you have determined that the recurrence relation for the travelling sales representative problem is $F(n) = (n - 1)F(n - 1) + 1$ with $F(1) = 1$.
[> rsolve( {F(n) = (n - 1)*F(n - 1) + 1, F(1) = 1}, {F(n)} );
$\{F(n) = e\Gamma(n,1)\}$
You look this up, and you note that this is the an incomplete Gamma function, and reading this up, you see this deals with hypergeometric functions, and being a second year engineering student, you'd just like to know what the asymptotic growth is, so you use series(...):
[> growth := rhs( %[1] ): [> series( growth, n = infinity, 1 );
$growth := \frac {\sqrt {2}\sqrt {\pi}{\rm e}\sqrt {{n}^{-1}}+\textrm{O} \left( \left( {n}^{-1} \right) ^{3/2} \right) }{ \left( {n}^{-1} \right) ^{n}{{\rm e}^{n}}}$
This looks awkward, so let's get rid of the error term by converting this to a polynomial:
[> growth := convert( growth, 'polynom' ): [> simplify( growth ) assuming n > 0;
$\sqrt {2}\sqrt {\pi}{{\rm e}^{1-n}}{n}^{n-1/2}$
From this, you see the growth is $\textrm{O}\left(e^{-n} n^{n - \frac{1}{2}}\right)$. You can hopefully see that this is likely not a strong candidate for an algorithm you'd like to implement.
For example, if you are solving the problem when $n = 1$ on a $4 \textrm{GHz}$ computer in a single clock cycle, then to solve a problem of size $n = 20$ requires approximately
[> simplify( exp(1)*GAMMA(20, 1);
$330665665962404000$
clock cycles. We can then determine how long this actually takes:
[> # How many seconds? [> %/4e9;
$0.8266641650 10^8$
[> # How many years? [> convert( %, 'units', 's', 'year' );
$2.619596679$
So, only two years, seven months and thirteen days, approximately.
Sorry, having some fun.