3. Evaluate the following recurrence relations and write down the big-O in terms of n. (20%) a. f(n)=2f(2n)+an,a is a constant and f(1)=1. b. f(n)=f(n1)+n2 and f(0)=1