GATE CSE
First time here? Checkout the FAQ!
x
+4 votes
172 views

How to solve this equation by the recursion tree method?

asked in Algorithms by (437 points)  
edited by | 172 views

4 Answers

+1 vote

by using master theorem.

answered by Boss (6.6k points)  
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.

 

answered by Junior (569 points)  
0 votes
According to master's theorem we are getting ans as o(n)
answered by Active (1.9k points)  
0 votes
Ans will be O(n).
answered by (35 points)  


Top Users Aug 2017
  1. ABKUNDAN

    4670 Points

  2. Bikram

    4556 Points

  3. akash.dinkar12

    3420 Points

  4. rahul sharma 5

    3124 Points

  5. manu00x

    2864 Points

  6. makhdoom ghaya

    2450 Points

  7. just_bhavana

    2136 Points

  8. Tesla!

    2042 Points

  9. stblue

    1930 Points

  10. joshi_nitish

    1686 Points


24,970 questions
32,072 answers
74,567 comments
30,150 users