hm, predposledni termin se blizi a ja porad nevim, kolik ma vyjit tohle. Uvaha "oba logaritmy jsou mensi jak jedna, tak vyhraje 3n a je to linearni" asi nebude spravna, nebot napriklad T(n) = T(n/2) + T(n/2) + n zrejme linearni neni.
Nejprve si vyjadris T(n) jako n^x a resis rovnici bez 3n na prave strane,
tj.: T(n) = T(n/3) + 3T(n/4)
Hledas nejvetsi x, ktere pro vsechna n splnuje:
n^x = (n/3)^x + 3(n/4)^x
1 = 1/(3^x) + 3/(4^x) = L(x)
Pro x>=2 je L(x) < 1.
Pro x=1 je L(x) > 1.
Maximalni x, ktere splnuje tuto rovnici, je teda v otevrenem
intervalu (1;2).
Protoze x > 1, tak vysledek je, ze T(n)=theta(n^x) .
Je divny, ze x vychazi tak blbe, tj. ze to neni nejake pekne cislo,
napr. 1 nebo 2. Mozna byla chyba v zadani zkousky.