1. u should calculate the k variable, that is
if i+j=3 (i=1, j=2, or vice versa) then k=3
if i+j=4 (i=1, j=3, or vice versa) then k=2
if i+j=5 (i=2, j=3, or vice versa) then k=1
2. the last question give the answer to the last 2:
T(m) = 1 if n = 1
2*T(m - 1) + 1 if n > 1
is the reccurence relation
T(m) = 2^m - 1 is the explicit formula.
by induction:
let's say T(k)=2^k - 1
we need to prove that <<T(k+1)=2^(k+1) -1>>
T(k+1)=2*T(k)+1 from the reccurence relation
but, we already have T(k)
T(k+1)=2*(2^k-1)+1=
2*2^k -2 +1=
2^(k+1) -1
What we needed to prove!
We just have to show that its true for k=1:
<<by definition>> T(1)=1 <<==>> <<2^k - 1>> 2^1-1=2-1=1
ok?
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
