I'm not sure which way is best to solve $$T(n)=5T(n/5) + n$$
(recursion tree/master method/recurrence?) I would like some assistance, which way is easier and how can I be sure I got the right answer (finding the asymptotic behavior)?
A drill down on a solution will be very appreciated.
Best Answer
Assuming $T(1)=t$, we find
$$T(5)=5t+5=5(t+1)\\ T(25)=25(t+1)+25=25(t+2)\\ T(125)=125(t+2)+125=125(t+3)\\ T(625)=625(t+3)+625=625(t+4)\\ \cdots\\ T(5^k)=5^k(t+k-1)+5^k=5^k(t+k),$$ or $$T(n)=n(t+\log_5n)$$ when $n$ is a power of $5$.
If you want to check an answer like $\Theta(n\log n)$, the first thing to do is to plug the function into the recurrence:
$$T(n)=n\log(n)\leftrightarrow5\frac n5\log(\frac n5)+n=n\log(n)+n(1-\log 5).$$
As the second term has a lower growth rate, it can be ignored, and the equality holds asymptotically. (Not counting the fact that when base $5$ logarithm is used, the agreement is perfect.)
Note that this method doesn't provide a total guarantee, it can only reveal grossly wrong formulas.