Równanie rekurencyjne - metoda podstawiania

[bartex9]

Witam,
Mam do rozwiązania takie zadanie i kompletnie nie wiem jak się do niego zabrać. Z góry wielkie dzięki za pomoc.

Korzystając, z metody podstawiania pokaż, że rozwiązaniem równania rekurencyjnego

\(\displaystyle{ T(n)= \begin{cases} \Theta(1); n=1 \\ 2T( \frac{n}{2})+\Theta(n); n>1 \end{cases}}\)

jest \(\displaystyle{ T(n)=\Theta(nlgn)}\) gdzie \(\displaystyle{ lg=log _{2}}\)

[maciejsporysz]

A czy możesz wyjaśnić, czy zadanie jest rozpatrywane w naturalnej dziedzinie (\(\displaystyle{ n \in N}\))?
I druga rzecz, czy masz przepis na funkcję \(\displaystyle{ \Theta}\) ?

[bartex9]

Nic więcej niestety nie wiem. To całe polecenie jakie dostałem. Dziedzina jest naturalna.

[maciejsporysz]

Pytam, bo tu mam wątpliwości
1. \(\displaystyle{ T(1)=\Theta (1)}\)
\(\displaystyle{ T(2)=\Theta (1) +\Theta (2)}\)
Jak to dodać skoro nic nie wiadomo o funkcji \(\displaystyle{ \Theta}\)
2 Jak policzyć \(\displaystyle{ T(\frac{3}{2})}\) skoro dziedzina jest naturalna ?

[bartex9]

No ja niestety nie mam pojęcia. Jak już pisałem to całe polecenie.