Problem 1

Recurrence

Define T(n) for n € Z+ by the recurr

T(n) =

recurrence

for n = 1

{7 (41) +1

T (1) + 1

for n ≥ 2

log(n) for all n ≥ 1, and hence, T(n) = N(log(n)).

Prove that T(n)

(1)