Wählen Sie Konstant für den letzten Schritt in der Substitutionsmethode $ T (n)= 5t (N / 4) + N ^ 2 $

Question

Ich habe eine Lösung für eine Rezidivbeziehung herausgefunden, aber ich bin nicht sicher, was die Konstante für den letzten Schritt sein sollte, um sich zu halten.

$ t (n)= 5t (n / 4) + n ^ 2 $

raten: $ t (n)= o (n ^ 2) $

Beweise: $ t (n) \ leq cn ^ 2 $

Zusammenbruch

$ t (n) \ leq 5 (c (n / 4) ^ 2) + n ^ 2 $

$= (5/16) cn ^ 2 + n ^ 2 $

$ \ leq cn ^ 2 $

Für den letzten Schritt, um sich zu halten, bin ich nicht sicher, was der Wert von c wegen der (5/16) sein sollte.Meine Vermutung wäre c>= 1 und ich bin mir nicht sicher, ob das halten würde.

Answer 1

Ihre konstante $ C $ muss befriedigen $$ \ frac {5} {16} c n ^ 2 + n ^ 2 \ leq c n ^ 2, $$ das ist, $$ \ frac {5} {16} C + 1 \ leq c.$$ Hoffentlich können Sie den Satz von Konstanten ermitteln $ C $ , für die diese Ungleichheit erfüllt ist.

Answer 2

$$ t (n)= 5t \ links (\ frac {n} {4} \ rechts) + n ^ 2= 5 ^ 2t \ links (\ frac {n} {4 ^ 2} \ rechts) + \ links (\ frac {5} {16} +1 \ rechts) n ^ 2= \\= 5 ^ 3t \ linke (\ frac {n} {4 ^ 3} \Rechts) + \ links (\ linke (\ frac {5} {16} \ rechts) ^ 2 + \ frac {5} {16 \ frac {5} {16} +1 \ rechts) n ^ 2=cdots= \\ = 5 ^ kt \ links (\ frac {n} {4 ^ k} \ rechts) + \ links (\ linke (\ frac {5} {16} \ rechts) ^ {k-1} + \ CDs + \ frac{5} {16} +1 \ rechts) n ^ 2 $$ Wenn Sie einen anfänglichen Zustand für $ T (1) $ haben, gehen wir an, $ n= 4 ^ k \ leftrightarrow k=\ log_ {4} n $ , dann erhalten wir $$ t (n)= 5 ^ kt (1) + n ^ 2 \ frac {16} {11} \ links (1- \ links (\ frac {5} {16)} \ rechts) ^ {k-1} \ rechts) \ in o (n ^ 2) $$