So I've been trying my best to do this, and I have made some good progress, I just need to know if what I have done is correct and if not, what the hell am I doing wrong? :P
I start off with this recurrence relation:
$$ T(n) = 2T(n/2) + 7 $$
for all n > 1, and n is some power of 2 and T(1) = 0.
I started out, by working going backwards, and getting a feel for the relation:
$$ T(n/2) = 2T(n/4) + 7 $$ $$ T(n/4) = 2T(n/8) + 7 $$ $$ T(n/8) = 2T(n/16) + 7 $$
Then I started substituting values upwards, so I started here:
$$ T(n) = 2(2T(n/2^2) + 7) + 7 = 2^2T(n / 2^2) + (2 * 7) + 7 $$ $$ T(n) = 2^2(2T(n/2^3) + 7) + (2 * 7) + 7 = 2^3T(n/2^3) + (2^2 * 7) + (2 * 7) + 7 $$
At that point I started to see a pattern emerging, and decided to try and get the general case:
$$ T(n) = 2^kT(n/2^k) + (2^{k-1} * 7) + (2^{k-2} * 7) \cdot\cdot\cdot + (2^0 * 7) $$
My next move was to use some knowledge that I already have. I already know that n is a power of 2, so it means:
$$ T(n) = 2^kT(2^k/2^k) = 2^kT(1) = 0 $$
So I am left with:
$$ T(n) = (2^{k-1} * 7) + (2^{k-2} * 7) \cdot\cdot\cdot + (2^0 * 7) $$
From here I decided to find the sum of the geometric progression, by first factoring out 7, so I am left with: $$ T(n) = 7(2^{k-1} + 2^{k-2} + 2^{k-3} \cdot\cdot\cdot 2^0) $$
Using this formula:
$$ (r^{n+1} - 1)/(r - 1) $$
Where r is the ratio, n is the number of elements in the sequence, I plugged in some values:
$$ (2^{k-1 + 1} - 1)/(2 - 1) $$
And I simplified:
$$ 2^k - 1 $$
I then replaced k with it's logarithm of n:
$$ 2^{log_2 n} - 1 $$
I then used a logarithmic identity to simplify further.
$$ n^{log_2 2} - 1 = n - 1 $$
Then included the 7 from way before:
$$ T(n) = 7(n-1) $$
And This is where I've stopped, because I'm stuck. Does this mean I conclude that the recurrence relation from the start has a linear complexity?
Your conclusion is correct. It is probably easier to build up from the bottom: $$\begin {array}{r r}n&T(n)\\1&0\\2&7\\4&21\\8&49\\16&105\\32&217 \end {array}$$ It sure looks like $T(n)=7(n-1)$. You can prove it with induction. It is true for $n=1$ Assuming it is true for $n$, we have $T(2n)=2T(n)+7=2\cdot 7(n-1)+7=7(2n-1)$