WEEK #6 @ T(n)

upper bound on T(n):

 T(n) >= c ·lgn  if c<=1

T(n) = 1     , n = 1
T(n) = 1 + T ⌈n / 2⌉ ,   n > 1

T(n) = 1-c + c· lg(n - 1)

it is possible to prove it by complete induction