найти сложность по времени для заданного рекуррентного отношения T (n) = T (√n) + n

Question

может кто-нибудь помочь мне с этим

с учетом рекуррентного отношения T(n)=T(√n)+n

Мне нужно оценить его временную сложность.Я сделал следующее:

given T(n)=T(√n)+n
        =>T(n-1)=T(√(n-1))+(n-1)  
        T(n)=T(sqrt(n-1))+(n-1)+n; 
        similarily evaluated T(n-2),
        T(n-3),.......

        => T(n)=T(√(n-k))+(n-k)+(n-(k-1))+.......+(n-1)+n
         assumed n-k=0
        =>n=k;
        =>T(n)=T(√(k-k))+(n-(n-1))+(n-(n-2))+......+(n-1)+n
        =>T(n)=T(0)+1+2+3+......+n
        =>T(n)=base case + Σn
        =>T(n)=constant + n(n+1)/2
        =>T(n)=O(n^2)

это правильно?

Answer 1

Согласно ответу здесь вы можете заменить:

, поэтому имеем:

Тогда повторение будетбыть как:

Тогда мы можем изменить представление:

и в соответствии с третьим случаем Теорема магистра сложность времени составит: