Решение рецидивов соотношения $ t (n) \ leq \ sqrt {n} t (\ sqrt {n}) + n $

Question

Учитывая условие: $ t (o (1))= o (1) $ и $ t (n) \ leq \ sqrt {n} t (\ sqrt {n}) + n $ .Мне нужно решить это отношение рецидива.Самая сложная часть для меня - количество подпроблем $ \ sqrt {n} $ не является константой, очень сложно применить метод дерева и основную теорему здесь.Любой намек?Моя мысль в том, что пусть $ c=sqrt {n} $ такое, что $ C ^ 2= n $ Итак, у нас есть $ T (C ^ 2) \ leq ct (c) + c ^ 2 $ Но я не выгляжу хорошо.

Answer 1

Пусть $ k= k (n) $ Будьте наименьшего положительного целого числа такого, что $ n ^ {2 ^ {-kk}} <2 $ .Эквивалентно $ k $ - это наименьшее положительное целое число, такое, что $ k> \ log_2 (\ log_2 (n)) $ .Итак, $$ k=lceil \ log_2 (\ log_2 (n)) \ rceil $$ Используя неоднократно неравенство с $ N, N ^ {2 ^ {- 1}}, n ^ {2 ^ {- 2}}, ..., n ^ {2 ^ {-kk}} $ мы получаем $$ \ begin {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) + кН \\ & \ 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} $$

Итак, мы получаем это $$ t (n) \ in o (n \ log_2 (\ log_2 (n))) $$