대체 방법의 마지막 단계에 대한 상수 선택 $ T (n)= 5t (n / 4) + n ^ 2 $

Question

재발성 관계에 대한 해결책을 알아 냈지만 마지막 단계에 대해 상수가 무엇을해야하는지 모르겠습니다.

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

추측 : $ t (n)= o (n ^ 2) $

증명 : $ T (n) \ LEQ CN ^ 2 $

고장

$ T (N) \ LEQ 5 (C (n / 4) ^ 2) + n ^ 2 $

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

$ \ leq CN ^ 2 $

마지막 단계를 보유하고있는 것은 (5/16) 때문에 C의 가치가 무엇인지 확실하지 않습니다.내 추측은 c>= 1 일 것입니다. 그 짓을하는지 확실하지 않습니다.

Answer 1

상수 $ C $ 만족해야합니다. $$ \ FRAC {5} {16} c \ 2 + n ^ 2 \ leq c n ^ 2, $$ 그건, $$ \ FRAC {5} {16} C + 1 \ LEQ C.$$ 바라건대이 불평등이 만족되는 상수 $ C $ 의 집합을 결정할 수 있습니다.

Answer 2

$$ T (n)= 5t \ left (\ frac {n} {4} \ \ frast) + n ^ 2= 5 ^ 2t \ left (\ frac {n} {4 ^ 2} \ Right) + \ left (\ frac {5} {16} +1 \ righ) n ^ 2= \\= 5 ^ 3t \ left (\ frac {n} {4 ^ 3} \오른쪽) + \ left (\ flac {5} {16} \ \ right) ^ 2 + \ frac {5} {16} +1 \ right) n ^ 2=cdots= \\ = 5 ^ kt \ left (\ frac {n} {4 ^ k} \ reign) + \ left (\ left (\ frac {5} {16} \ righ) ^ {k-1} + \ cdots + \ frac{5} {16} +1 \ 오른쪽) n ^ 2 $$ $ T (1) $ 에 대한 초기 조건이 있고 $ n= 4 ^ K \ Leftrightarrow k=\ log_ {4} n $ 을, 다음 우리는 얻습니다. $$ t (n)= 5 kt (1) + n ^ 2 \ frac {16} {11} \ left (1- \ 왼쪽 (\ frac {5} {16)} \ right) ^ {k-1} \ right) \ in (n ^ 2) $$