доказательства для рекуррентных соотношений

[Vredinka]

Ребятки, помогите пожалуйста.... ооочень надо.
Надо доказать методом итераций , что для рекуррентного соотношения
$T(n)=2T(n/2)+n$
истинно
$T(n)=\Theta (n\log n)$

А для
$T(n)=T(n-1)+n$
истинно
$T(n)=\Theta(n^2/2)$

Спасибо вам огромное за помощь!

от модератора GAA:

Дублирование сообщений, набор любых формул без использования системы набора $\TeX$, небрежная формулировка задачи и отсутствие попыток решения --- являются нарушениями правил форума. По совокупности --- строгое предупреждение.

Продемонстрируйте попытки решения. Укажите конкретные затруднения.

[Padawan]

По поводу первого -- уточните область определения функции $T(n)$.

[ewert]

(для разнооднообразия) и область смыслов функции "квадратик" тоже

[Vredinka]

к сожалению, ничем дополнить не могу т.к. это полное задание, которое есть.

[Mathusic]

ewert в сообщении #335341 писал(а):

(для разнооднообразия) и область смыслов функции "квадратик" тоже

(Оффтоп)

Вы про этот Ѳ греческий покемон что ли?

[Padawan]

В общем идея такая: начиная с некоторого большого $n$ мы постепенно двигаемся согласно рекуррентной формуле к $n=1$, ну или к каким-то начальным значениям $n=n_0$. Надо оценить количество таких шагов, а потом, двигаясь в обратном порядке, прикинуть как может вырасти $T$ от $T(n_0)$ до $T(n)$.

[Vredinka]

квадратик - это тета ("сложность")

//Отредактировал первое сообщение. / GAA

[neo66]

Vredinka в сообщении #335356 писал(а):

квадратик - это тета ("сложность")

А "сложность" - это что такое?

А, нашел в Википедии, имеется в виду сложность алгоритма. Правда, не понятно, какого алгоритма.
В, общем, рискну предположить, что автор что-то перепутал или не понял.

[venco]

Да не, вроде понятно.
$T(n)$ время выполнения алогритма на данных размера $n$.
Из рекурсивного определения $T(n)$ надо определить сложность алгоритма.
Доказывается подстановкой предполагаемой сложности, исходя из определения сложности $T(n) < Const\cdot \Theta(n)$.

[Xaositect]

venco в сообщении #335392 писал(а):

исходя из определения сложности $T(n) < Const\cdot \Theta(n)$.

Что-то не то Вы говорите.
По определению, $f = \Theta(g)$, если $f = O(g)$ и $g = O(f)$


А доказывается по индукции, что такое "метод итераций" - непонятно.
По поводу первого соотношения, можете погуглить доказательство Master theorem.

[st256]

Vredinka в сообщении #335335 писал(а):

Ребятки, помогите пожалуйста.... ооочень надо.
Надо доказать методом итераций , что для рекуррентного соотношения
$T(n)=2T(n/2)+n$

истинно
$T(n)=\Theta (n\log n)$

А для
$T(n)=T(n-1)+n$

истинно
$T(n)=\Theta(n^2/2)$

БПФ?

[Vredinka]

Спасибо за помощь