Вывести рекуррентное соотношение.

[Vredinka]

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

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

истинно
T(n)=Ѳ(n^2/2)
Огромное вам спасибо за помощь! ;)

[ewert]

Что такое "метод итераций" -- это загадка. Вообще-то подобные вещи легко доказываются методом математической индукции. Только сначала надо всё же сказать, что это за операция такая -- "квадратик".

[Vredinka]

какой "квадратик" ? возможно тета не отобразилась? в задании именно методом итераций надо доказать:(

[ewert]

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

возможно тета не отобразилась?

Возможно и не отобразилось. Однако с тетой -- лучше не станет. Эта буковка по контексту может означать всё что угодно, но только не то, что, очевидно, подразумевалось в этих задачах (даже несмотря на то, что так толком и неизвестно, что в точности подразумевалось).

[Vredinka]

как я поняла, тета - это "сложность".

//Дубль. Эта ветка закрыта и будет удалена. /GAA