Scegliere costante per l'ultimo passo nel metodo di sostituzione $ t (n)= 5t (N / 4) + n ^ 2 $

Question

Ho capito una soluzione a una relazione di ricorrenza, ma non sono sicuro di cosa dovrebbe essere la costante per l'ultimo passo da tenere.

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

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

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

Breakdown

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

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

$ \ leq cn ^ 2 $

Per l'ultimo passo per tenere non sono sicuro di quale sia il valore di C a causa del (5/16).La mia ipotesi sarebbe c>= 1 e non sono sicuro se ciò sarebbe stato.

Answer 1

La tua costante $ c $ deve soddisfare $$ \ frac {5} {16} c n ^ 2 + n ^ 2 \ leq c n ^ 2, $$ questo è, $$ \ frac {5} {16} c + 1 \ leq c.$$ Spero che tu possa determinare il set di costanti $ c $ per il quale questa disuguaglianza è soddisfatta.

Answer 2

$$ t (n)= 5t \ sinistra (\ frac {n} {4} \ destra) + n ^ 2= 5 ^ 2t \ sinistra (\ frac {n} {4 ^ 2} \ destra) + \ \ sinistra (\ frac {5} {16} +1 \ destra) n ^ 2= \\= 5 ^ 3t \ sinistra (\ frac {n} {4 ^ 3} \Destra) + \ sinistra (\ sinistra (\ frac {5} {16} \ destra) ^ 2 + \ frac {5} {16} +1 \ destra) n ^ 2=cdots= \\ = 5 ^ kt \ sinistra (\ frac {n} {4 ^ k} \ destra) + \ sinistra (\ sinistra (\ frac {5} {16} \ destra) ^ {k-1} + \ cdots + \ frac{5} {16} +1 \ destra) n ^ 2 $$ Se hai qualche condizione iniziale per $ t (1) $ e assumiamo $ n= 4 ^ k \ leftrightarrow k=\ log_ {4} n $ , quindi otteniamo $$ t (n)= 5 ^ kt (1) + n ^ 2 \ frac {16} {11} \ sinistra (1- \ sinistra (\ frac {5} {16} \ destra) ^ {k-1} \ destra) \ in o (n ^ 2) $$