retagged by
1,180 views

4 Answers

0 votes
0 votes

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.

Related questions