Resolvendo relação de recorrência $ t (n) \ leq \ sqrt {n} t (\ sqrt {n}) + n $

Question

Dada a condição: $ t (o (1))= O (1) $ e $ t (n) \ leq \ sqrt {n} t (\ sqrt {n}) + n $ .Eu preciso resolver esta relação de recorrência.A parte mais difícil para mim é o número de subproblemas $ \ sqrt {n} $ não é uma constante, é realmente difícil aplicar o método de árvore e o teorema mestre aqui.Qualquer dica?Meu pensamento é que deixe $ c=sqrt {n} $ tal que $ c ^ 2= n $ por isso temos $ t (c) \ leq ct (c) + c ^ 2 $ mas eu não pareço bom.

Answer 1

Deixe $ k= k (n) $ seja o menor inteiro positivo tal que $ n ^ {2 ^ {{^ {-k}} <2 $ .Equivalentemente $ k $ é o menor inteiro positivo, tal que $ k> \ log_2 (\ log_2 (n)) $ .Então, $$ k=lceil \ log_2 (\ log_2 (n)) \ rceil $$ Usando repetidamente a desigualdade com $ n, n ^ {2 ^ {- 1}}, n ^}, n ^}}, ..., n ^ {2 ^ {}-k}} $ nós recebemos $$ \ begin {alinhar} 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)) \ fim {alinhar} $$

Então, obtemos aquela $$ t (n) \ in O (n \ log_2 (\ log_2 (n))) $$