Zadání bylo podle mého triviální. Ale tak jestli bylo se ukáže na ústní části v jednu :D
Odhadnout f(n) takové, že T(n) = T(n/3) + 2T(n/4) + 3n náleží theta(f(n)) a dokázat substituční metodou; navíc předpokládáme, že pro vhodné n0 T(n0) je O(1).
Platí/neplatí: Y je cesta od kořene k listu v AVL-stromu. X je množina prvků vlevo od Y, Z množina prvků vpravo od Y. Pak pro každé x z X, y z Y a z ze Z platí:
klíč(x) <= klíč(y) <= klíč(z).Platí/neplatí: máme orientovaný graf, v něm vrchol u, jehož vstupní i výstupní stupeň je >=1. Potom každý DFS strom, do něhož náleží u, má alespoň dva vrcholy. Navíc G neobsahuje smyčky.
Můj názor
f(n) = n; položíme n0 = 12. Vyjde z IP že d>=12, c<=6, potom pro n-->n+1 vyjde c<=18, d>=18, tedy pro n>=12 6n <= T(n) <= 18(n).
neplatí; obecně platí jen pro x, y a z ze stejné hladiny podstromu, vtip je v tom, že y může být otcem x nebo z, ale nepřímým, tudíž x může být v pravém podstromu y a vice versa
platí; buď byl u od někud objeven a tedy DFS strom má kořen různý od u, tedy má vrcholy alespoň dva, nebo DFS v u začínalo a došlo do některého ze sousedních vrcholů, které existují, protože podle zadání deg out (u) >= 1 a na u není smyčka.