TAL - úkol 1 (Demlová) - 2013/2014

Zadání úkolu č.1 (Demlová)

Bez záruky, kdo ví víc, nechť opraví či doplní :)

1) Neplatí. Museli bychom najít takovou konstantu c, pro kterou by platilo:

  3^2n <= c * 3^n (prostě definice O)
  3^n * 3^n <= c * 3^n
  3^n <= c

Takovou konstantu asi nenajdeme.
Viz také: http://math.stackexchange.com/questions/131420/is-22n-o2n, http://www.daniweb.com/software-development/computer-science/threads/411690/22n-o2n-true-or-false

2) Platí, jelikož mezi tím platí tranzitivita.

3) Můžeme použít Master Theorem, konkrétně jde o 2.případ, vychází to O(n.lg n)

4) Tady Master Theorem nejspíš použít nejde (ačkoliv jsem viděl podobné příklady, kde to nějak ohackovali a Master Theorem použili, ale moc jsem to nepobral). Tady se chce asi použít třeba ta „metoda“ rekurzivních stromů z přednášky. Snažil jsem se to udělat jako v příkladech z přednášky, vyjádřil jsem součet přes celý strom (tj. tu složitost) pomocí geometrické posloupnosti (počet jejích členů je log2(n) - tedy lg(n), protože n se dělí vždy 2) a pak jí sečetl přes známý vzoreček pro součet. Vyšlo mi to O(n^2), jestli je to dobře nevím.

5) Předpoklad je špatně? Ta suma je aritmetická posloupnost, když si podle známého vzorečku na součet spočteme její součet, zjistíme že je to (n+n^2)/2, což je O(n^2) a ne O(n). Podle mě je špatně to vyhodnocení té indukce, protože ten krok n+1 má složitost O(1) takže je to O(n) + O(1) = O(n + 1) a konstantu zanedbáme.