Szacowanie złożoności rekurencyjnej

Jak i jakim sposobem oszacować poniższe złożoności rekurencyjne:

1. T(n)= T(n-1) + lgn
2. T(n)= sqrt(n) + T(sqrt(n))+1

Jeśli warunkiem zakończenia 1 jest n = 1 to mi sił wydaje, że to jest O(n), bo można to zapisać jako:

FOR x IN n..0
    sum = sum + log(n)
END

Niestety Twoja odpowiedź jest zła.
Wynik dla 1 to O(log^2n) niestety nie wiem jak do niego dotrzeć.
Chcę podstawić n=2^k i policzyć sumę logarytmów ale nie wiem czy dobrze to robię.

Dla mnie w 1. powinno wyjść około n lg n. lg (n / 2) = lg n - 1, a więc T(n) > n * (lg n - 1) / 2 + T(n / 2)
W 2. stawiałbym na O(sqrt(n))

Oczywiście że w 1 jest Theta(nlogn), milion sposobów, żeby to pokazać, np. rozwiń wyraz na T(n) n-1 razy dostaniesz sumę logarytmów która wynosi ln(n!), a to jest nlogn.

W drugim znowu jak sobie na pałę rozwiniemy to otrzymujemy sumę pierwiastków, liczba tych elementów jest koło log(log(n)) i można to oszacować, albo jeszczę łatwiej można za n podstawić 2^{k, wtedy złożoność zostaje ta sama i mamy T(2}k) = T(2^{{k-1}) + 2}{k-1} +1, podstawiamy G(k) = T(2^{k) i otrzymujemy G(k) = G(k-1) + 2}{k-1} + 1, a rozwiązanie tego ze względu na k jest Theta(2^k), zatem wyjściowej rekurencji Theta(n).

literówka, chodziło mi o podstawienie n = 2^{2k}, wtedy mamy G(k) = G(2^{2k}), zatem G(k) = G(k-1) + 2^{2{k-1}} +1, rozwiązanie asymptotycznie to sum_{i=1}^{{k-1} 2}{2^{i}, szacując bardzo z góry możemy to oszacować przez sum_{i=1}}{2^{{k-1}} 2}i = 2^{2{k-1}+1} - 1 co jest asymptotycznie równe sqrt(n), z dołu przez sqrt(n) jest jasne, więc rozwiązaniem jest Theta(sqrt(n))

No to miałem rację :)