AiSD rekurencje

madaf007
Użytkownik
Użytkownik
Posty: 131
Rejestracja: 4 wrz 2008, o 17:01
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 33 razy

AiSD rekurencje

Post autor: madaf007 »

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.
ODPOWIEDZ