172 views

How to solve this equation by the recursion tree method?

$T(n)=5T(\frac{n}{5})+\sqrt{n}$

edited | 172 views

+1 vote

by using master theorem.

Not all question are solved by reccurence tree method. Here Master Theorem is efficent for us.

But,You can think of your recurrence as being a tree. The top level takes  sqrt(n) steps. At the next level, you have five different calls, and each one takes sqrt(n/5 ) steps. The next level has 9 different calls, and so on, until you reach your base case.
The total work done is the sum of the work at each level.

According to master's theorem we are getting ans as o(n)
Ans will be O(n).

1
2