Résolution de la récurrence Relation $ T (n) \ Leq \ sqrt {n} t (\ sqrt {n}) + n $

Question

donné la condition: $ t (o (1))= O (1) $ et $ t (n) \ Leq \ sqrt {n} t (\ sqrt {n}) + n $ .J'ai besoin de résoudre cette relation de récurrence.La partie la plus difficile pour moi est le nombre de subproblèmes $ \ sqrt {n} $ $ n'est pas une constante, il est vraiment difficile d'appliquer la méthode des arbres et le théorème maître ici.Toute astuce?Ma pensée est que laissez $ c=sqrt {n} $ tel que $ C ^ 2= n $ Nous avons donc $ t (c ^ 2) \ Leq ct (c) + c ^ 2 $ mais je n'ai pas l'air bien.

Answer 1

let $ k= k (n) $ est le plus petit entier positif de telle que $ n ^ {2 ^ {-k}} <2 $ .Équivalent $ k $ est le plus petit entier positif de telle que $ k> \ log_2 (\ log_2 (n) $) $ .Donc, $$ k=lceil \ log_2 (\ log_2 (n)) \ rceil $$ En utilisant à plusieurs reprises l'inégalité avec $ n, n ^ {2 ^ {- 1}}, n ^ {2 ^ {- 2}}, ..., n ^ {2 ^ {-k}} $ nous obtenons $$ \ commencer {align} T (n) & \ leq n ^ {1/2} t (n ^ {1/2}) + n \\ & \ Leq n ^ ^ {1/2 + 1/4} T (n ^ {1/4}) + 2n \\ & \ Leq n ^ ^ {1/2 + 1/4 + 1/8} T (n ^ {1/8}) + 3n \\ & ... \\ & \ Leq n ^ ^ {1/2 + 1/4 + ... + 1/2 ^ k} T (n ^ {2 ^ {- k}}) + kn \\ &= n ^ {1-2 ^ {- k}} O (1) + kn \\ & \ Leq n ^ ^ ^ {1-1 / \ log_2 (n)} o (1) + n \ log_2 (\ log_2 (n)) \\ &=frac {n} {2} o (1) + n \ log_2 (\ log_2 (n)) \ fin {align} $$

Alors, nous obtenons cette $$ t (n) \ in o (n \ log_2 (\ log_2 (n))) $$