Risoluzione della relazione di ricorrenza $ t (n) \ leq \ sqrt {n} t (\ sqrt {n}) + n $

Question

Dato la condizione: $ t (o (1))= o (1) $ e $ t (n) \ Leq \ SQRT {N} T (\ SQRT {N}) + N $ .Ho bisogno di risolvere questa relazione di ricorrenza.La parte più difficile per me è il numero di subproblems $ \ sqrt {n} $ non è una costante, è davvero difficile applicare il metodo dell'albero e il teorema master.Qualche suggerimento?Il mio pensiero è che let $ c=sqrt {n} $ in modo tale che $ c ^ 2= n $ Quindi abbiamo $ t (c ^ 2) \ leq ct (c) + c ^ 2 $ ma non sembra buono.

Answer 1

Let $ k= k (n) $ Sii il più piccolo intero positivo in modo tale da $ n ^ {2 ^ {-k}} <2 $ .Equivalentemente $ k $ è il più piccolo numero intero positivo in modo tale da $ k> \ log_2 (\ log_2 (n)) $ .Quindi, $$ k=lceil \ log_2 (\ log_2 (n)) \ rceil $$ Utilizzando ripetutamente la disuguaglianza con $ n, n ^ {2 ^ {- 1}}, n ^ {2 ^ {- 2}}, ..., n ^ {2 ^ {-k}} $ otteniamo $$ \ Begin {allinea} 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)) \ end {allinea} $$

Quindi, otteniamo quella $$ t (n) \ in o (n \ log_2 (\ log_2 (n))) $$