Question

Do expand-guess-verify technique for the following relationships, show step by step.

Find closed-form formula for these recursive relationships. Estimate running time complexity (Big Oh) of the closed-form formulas – those also give you idea how “good” or “bad” original recursive algorithms are!

1. f(1) = 5
   f(n) = f(n-1) + 4
2. f(1) = 2
   f(n) = 3f(n-1)

Answer 1