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? 😛
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?
Best Answer
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)$