When I apply master theorem, I get O(n) but when I try to solve it using recursion tree, I get stuck and couldn't make out any solution.
I tried this :
T(n) = 5T(n/5) + sqrt(n)
T(n) = 5(5T(n/25) + sqrt(n/5)) + sqrt(n)
= 25T(n/25) + sqrt(5n) + sqrt(n)
T(n) = 5(5(5T(n/125) + sqrt(n/25)) + sqrt(n/5)) + sqrt(n)
= 125T(n/25) + sqrt(25) + sqrt(5n) + sqrt(n)
.
.
.
T(n) = sqrt(n) + sqrt(5n) + sqrt(25n) + sqrt(125n) + sqrt(625n) + sqrt(3125n) + ...
How do I suppose to solve this GP??
The final sum has log_5(n) + O(1) terms, since the recursion bottoms out. The largest is sqrt(5^(log_5(n) + O(1)) n) = sqrt(O(n) n) = O(n). The others decrease geometrically, so they don't matter in the big-O accounting (alternatively, divide through by 1 + sqrt(1/5) + sqrt(1/5^2) + ... = Theta(1)).