i) Consider the assertions below. Prove or disprove the assertion using limits, possibly with LHopitals rule. Also, if the assertion is true, show that it is true directly from the definition of the asymptotic notation and derive values for the relevant constants.

(a) 3n^2 + 5n + 7 O(n2)

(b) 5(n 2)! (n!)

(c) cubicSqrt(n^3 5) (n) ( n^3-5 is under a cubic square root )

ii) Give the recurrence relation where indicated or solve the given recurrence relation by algebraically unrolling it.

(a) Give a recurrence relation, T(n), and its initial condition for the sequence 3, 5, 9, 17, 33, 65 .

(b) Solve the relation in (a).

(c) Solve T(n) = cn + T(n 1) with the initial condition T(1) = 1.

(d) Solve T(n) = T(n / ) + n with the initial condition T(1)=1.