Resolver la relación de recurrencia $ t (n) \ leq \ sqrt {n} t (\ sqrt {n}) + n $

Question

Dada la condición: $ t (o (1))= o (1) $ y $ t (n) \ leq \ sqrt {n} t (\ sqrt {n}) + n $ .Necesito resolver esta relación de recurrencia.La parte más difícil para mí es la cantidad de subproblems $ \ sqrt {n} $ no es una constante, es realmente difícil aplicar el método del árbol y el maestro de teorema aquí.¿Algún consejo?Mi pensamiento es que deja que $ c=sqrt {n} $ tal que $ c ^ 2= n $ Así que tenemos $ t (c ^ 2) \ leq ct (c) + c ^ 2 $ pero no me veo bien.

Answer 1

Permitir $ k= k (n) $ ser el entero positivo más pequeño de tal que $ n ^ {2 ^ {-K}} <2 $ .Equivalentemente $ K $ es el entero positivo más pequeño de tal que $ k> \ log_2 (\ log_2 (n)) $ .Entonces, $$ k=lceil \ log_2 (\ log_2 (n)) \ rceil $$ Usando repetidamente la desigualdad con $ n, n ^ {2 ^ {- 1}}, n ^ {2 ^ {- 2}}, ..., N ^ {2 ^ {-k}} $ obtenemos $$ \ comienzan {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 \\ Y ... \\ & \ 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)) \ End {align} $$

Entonces, obtenemos esa $$ t (n) \ in o (n \ log_2 (\ log_2 (n))) $$