a.
For Evens:
Assume that n = 2m, m being an integer
F(2m + 1)/2) = C(2m/2)
F((2m/2) + (1/2)) = C(m)
C(m) = m
F(m + (1/2)) = m
m = m
For Odds:
Assume that 2 = (2m + 1), m being an integer
F(((2m + 1) + 1) / 2) = C(2m + 1) / 2))
F((2m + 2)/2) = C((2m/2) + (1/2))
F((2m/2) + (2/2)) = C(m + (1/2))
F(m+1) = C(m + (1/2))
F(m + 1) = (m + 1)
C(m + (1/2)) = (m + 1)
(m + 1) = (m + 1)
b.
For Evens:
Assume n = 2m, m being an integer
f(2m/2) + 1 = C((2m + 1) /2)
F(m) + 1 = C((2m/2) + (1/2))
F(m) = m
m + 1 = C(m + (1/2))
m + 1 = m + 1
For Odds:
Assume n = 2m + 1, m being an integer
F((2m + 1)/2) + 1 = C(((2m + 1) + 1) /2)
F((2m/2) + (1/2) + 1) = C((2m/2) + (2/2))
F(m + (1/2)) + 1 = C(m + 1) = m + 1
m + 1 = m + 1
c.
D(n) = T(n + 1) - T(n)
prove D(1) = 2:
D(1) = T(2) - T(1)
= T(F(1)) + T(C(1)) + 2 - 0
= T(1) + T(1) + 2
= 0 + 0 + 2
= 2
prove D(n) = T(n + 1) - T(n)
= T(F(n+1)/2) + T(C((n + 1)/2)) + n + 1 - (T(F(n/2)) + T(C(n/2)) + n)
= T(F ((n+1)/2))+T(C[(n+1)/2])+n+1- T(F[n/2])-T(C[n/2])-n
= T(F((n/2) + 1)/2)) + T(C((n+1)/2)) - T(F(n/2)) - T(C(n/2)) + 1
D(F(n/2)) + 1 = T(F(n/2) + 1) - T(F(n/2)) + 1
T(F(n/2) + 1) - T(F(n/2)) + 1 = T(F((n+1)/2)) + T(C((n+1)/2)) - T(C(n/2))
= T(F((n+1)/2)) - T(C(n/2))
= T(F((n+1)/2)) = T(C(n/2)
= T(F((n+1)/2)) = T(F((n+1)/2))
d.
D(n) = D(F(n/2)) + 1
= D(F(n/4)) + 1+ 1
= D(F(n/8)) + 1 + 1 + 1
= D(F(n/2k)) + k
let n = 2k and k = F(lg(n))
= D(1) + F(lg(n))
= F(lg(n)) + 2
e.
T(n) - T(1) = \(\Sigma_{k=1}^{n-1}\)(F(lg(k))
T(n) = D(1) + D(2) + D(3) + ... + D(n-1)
T(n) = T(2) - T(1) + T(3) - T(2) + T(4) - T(3) + ... + T(n) + T(n-1)
T(n) - T(1) = \(\Sigma_{k=1}^n\) - \(\Sigma_{k=1}^{n-1}\)
T(n) = T(n)
because we know that T(n) = \(\Sigma_{k=1}^{n-1}\)D(k), as well as D(n) = F(lg(n)) + 2,
T(n) = \(\Sigma_{k=1}^{n-1}\)F(lg(n)) + 2
f.
T(n) = \(\Sigma_{k=1}^{n-1}\)F(lg(n)) + \(\Sigma_{k=1}^{n-1}\)(2)
= \(\Sigma_{k=1}^{n-1}\)F(lg(n)) + 2(n - 1)
= \(\Sigma_{k=1}^{n-1}\)F(lg(n)) + 2n - 2
= nF(lg(n)) - 2F(lg(n))+ 1 + F(lg(n)) + 2
= 2n + (n-1) F(lg(n-1)) - 2F(lg(n-1)) 2 + F(lg(n-1))
= 2n + nlg(n-1) - 2F(lg(n-1)) * 2
if we make this big O, nlg(n) will dominate the terms, so we get O(nlg(n))