Notes

Let’s start with the recurrence relation, T(n) = 2 * T(n/2) + 2, and try to get it in a closed form. Note that ‘T’ stands for time, and therefore T(n) is a function of time that takes in input of size ‘n’.
T(n) = 2T(n/2) + 2
This is our first iteration, we will name our iterations as ‘k’ such that the first iteration means k=1, and the second means k=2 and so on. The ‘k’ value will be used later.
Now we need to figure out what T(n/2) is. We can do that by taking “n/2” , and putting it into our original function T(n), to get the following:
Note: We are just replacing n with n/2.
T(n/2) = 2T( (n/2) / 2) + 2
= 2T( n/4 ) + 2
So our original equation looks like the following when k= 2
T(n) = 2T(n/2) + 2
= 2( 2T( n/4 ) + 2) + 2
= 4T(n/4) + 4 + 2
That was our second iteration, so this means k=2 .Now we must figure out what T(n/4) is. We can do that by taking “n/4” , and putting it into our original function T(n), to get the following:
T(n/4) = 2T( (n/4) / 2 ) + 2
= 2T(n/8) + 2
So our original equation looks like the following when k=3
T(n) = 4T(n/4) + 4 + 2
= 4(2T(n/8) + 2) + 4 + 2
= 8T(n/8) + 8+ 4 + 2
That was our third iteration, so this means k=3 . Now we must figure out what T(n/8) is. We can do that by taking “n/8” , and putting it into our original function T(n), to get the following:
T(n/8) = 2T( (n/8) / 2 ) + 2
= 2T(n/16) + 2
So our original equation looks like the following when k=4
T(n) = 8T(n/8) + 8+ 4 + 2
=8(2T(n/16) + 2) + 8+ 4 + 2
= 16T(n/16)+16 + 8+ 4 + 2
That was our fourth iteration, so this means k=4 . Now we must figure out what T(n/16) is. We can do that by taking “n/8” , and putting it into our original function T(n), to get the following:
T(n/16) = 2T( (n/16) / 2 ) + 2
= 2T(n/32) + 2
So our original equation looks like the following when k=5
T(n) = 16T(n/16)+16 + 8+ 4 + 2
=16(2T(n/32) + 2)+16 + 8+ 4 + 2
= 32T(n/32)+ 32 +16 + 8+ 4 + 2
Okay let’s stop here and see if we can see a pattern, if not then you should continue this method or process until you do.
When k=1, we had T(n) = 2T(n/2) + 2
When k=2, we had T(n) = 4T(n/4) + 4 + 2
When k=3, we had T(n) = 8T(n/8) + 8+ 4 + 2
When k=4, we had T(n) = 16T(n/16)+16 + 8+ 4 + 2
When k=5, we had T(n) = 32T(n/32)+ 32 +16 + 8+ 4 + 2
Let’s rewrite this a little bit more to see if we can see a pattern.
When k=1, we had T(n) = 2T(n/2) + 2
= T(n) = 2T(n/2) + 2 →T(n) = 2T(n/2) + 2(1)
When k=2, we had T(n) = 4T(n/4) + 4 + 2
= T(n) = 4T(n/4) + 4 + 2 → T(n) = 4T(n/4) + 2(2 + 1)
When k=3, we had T(n) = 8T(n/8) + 8+ 4 + 2
= T(n) = 8T(n/8) + 8+ 4 + 2 → T(n) = 8T(n/8) + 2( 4 + 2 +1)
When k=4, we had T(n) = 16T(n/16)+16 + 8+ 4 + 2
= T(n) = 16T(n/16)+16 + 8+ 4 + 2 → T(n) = 16T(n/16)+2(8+ 4 + 2 +1)
When k=5, we had T(n) = 32T(n/32)+ 32 +16 + 8+ 4 + 2
=T(n) = 32T(n/32)+ 32 +16 + 8+ 4 + 2
= T(n) = 32T(n/32)+ 2 (16 + 8+ 4 + 2 + 1)
Notice the general form in terms of ‘k’ looks like:
T(n) = 2^k * T(n/ (2^k) + 2 *Summation from i=0 to k-1 of 2^i
The summation from i=0 to k-1 of 2^i is 2^(k) — 1.
So our general form looks like below:
T(n) = 2^k * T(n/ (2^k) )+ 2 *(2^k — 1)
T(n) = 2^k * T(n/ (2^k) )+ 2^(k+1) — 2
When does our recurrence relation stop ? Well it stops when T(n/(2^k)) hits the base case. You may say, but we were never given a base case. That’s okay because every recurrence relation has a base case, and it is always some constant value. So if a base case isn’t provided, we can make one up. So our base case will be T(1) = C, which means when our input is of size 1, the time it takes to execute the function ‘T’ is ‘C’ unit(s) of time, where ‘C’ is some constant unit of time. This means when n = 1, T(n=1) = C.
We must now get our T(n) function from our general form to stop, and therefore need T(n/(2^k))=C, this implies n/(2^k) must equal 1, since T(n/(2^k)=1) = C. Let’s do some algebra below.
= n/(2^k) = 1
= n = (2^k)
= log base 2 of n = k
We now not only have our stopping case, but can also put our value ‘k’ in terms of n, for the entire equation, by plugging in ‘log base 2 of n’ for ‘k’.
T(n) = 2^(log base 2 of n) * T(n/ (2^(log base 2 of n)) )+ 2 *(2^(log base 2 of n) — 1)
T(n) = n * T(n/n) + 2( n — 1)
T(n) = n T(1) + 2n — 2
T(n) = n*(C) + 2n — 2
T(n) = Cn + 2n — 2
T(n) = n ( C+2) — 2
So our guess is that the closed form of our recurrence relation is:
T(n) = n ( C+2) — 2, where C is some constant
NOTE: n ( C+2) — 2 is O(n)
If C = 0 then the equation is
T(n) = n(0 + 2) — 2
T(n) = 2n — 2 = 2( n-1)