Needs Algorithm Solution.

Let T(n) be a running time function defined recursively as

() = { 0, = 0

1, = 1

3( 1) 2( 2), > 1

a. Find a non-recursive formula for T(n).

b. Prove by induction that your answer in part (a) is correct.

c. Find a tight bound for T(n).