1.Pokaż, że rozwiązaniem równania \(\displaystyle{ T(n) = T(\lceil n/2 \rceil) + 1}\) jest O(lg n).
2. - || - \(\displaystyle{ T(n) = 2T(\lfloor n/2 \rfloor) + n}\) jest \(\displaystyle{ \Theta (n \ lg \ n)}\).
Udaje mi się tylko zrobić dla
\(\displaystyle{ T(n)\leqslant c2(\lfloor n/2 \rfloor lg\lfloor n/2 \rfloor) +n \leqslant cn lg(n/2) + n = cn(lgn - lg2) +n = cnlogn - cn + n\leqslant cnlog \ n}\)
dla c>1.
W drugą stronę nie mam pojęcia.
Proszę o pomoc.