GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
120 views

How to solve this equation by the recursion tree method?

asked in Algorithms by (417 points)  
edited by | 120 views

3 Answers

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 (549 points)  
0 votes
According to master's theorem we are getting ans as o(n)
answered by Junior (947 points)  
0 votes
Ans will be O(n).
answered by (35 points)  


Top Users Apr 2017
  1. akash.dinkar12

    3508 Points

  2. Divya Bharti

    2542 Points

  3. Deepthi_ts

    2040 Points

  4. rude

    1966 Points

  5. Tesla!

    1768 Points

  6. Shubham Sharma 2

    1610 Points

  7. Debashish Deka

    1588 Points

  8. Arunav Khare

    1454 Points

  9. Kapil

    1424 Points

  10. Arjun

    1420 Points

Monthly Topper: Rs. 500 gift card

22,076 questions
28,040 answers
63,230 comments
24,135 users