How do you calculate time complexity in case of recursion algorithms?
for eg t(n) = t(3n/2) + 0(1) (Heapsort)
Asked
Active
Viewed 849 times
1
ROMANIA_engineer
- 51,252
- 26
- 196
- 186
zedai
- 455
- 2
- 5
- 11
-
Dupe of http://stackoverflow.com/questions/2709106/time-complexity-of-a-recursive-algorithm – gioele Nov 03 '11 at 12:28
4 Answers
3
Use the Master Theorem.
Anyway, your equation looks broken, since recursive calls have higher input values than that of the caller, so your complexity is O(infinity).
Please fix it.
akappa
- 9,892
- 3
- 38
- 54
2
usually you can guess the answer and use induction to prove it.
but there is a theorem which solves a lot of situations as heap sort, named Master Theorem:
a-z
- 1,604
- 3
- 15
- 35
2
Master's theorm is the quick and short way. But since you are trying to learn the complexity for all recursive functions, I would rather suggest you to learn the working of recursion tree, which forms the foundation of Master's Theorm . This link goes on to explain it in detail. Rather than using the Master's theorm blindly, learn this for your better understanding in the future ! This link about recursion tree is a good read too
bsoundra
- 930
- 2
- 11
- 26
-
First link is http://www.google.com/url?sa=t&rct=j&q=proof%20for%20masters%20theorem&source=web&cd=3&ved=0CDIQFjAC&url=http://www.math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf&ei=rmmxTqDTE6HU2AW7l8XAAw&usg=AFQjCNGDmkEB1d_ClcH6IryDb3TB8kEN8Q&sig2=tzsKR1FJEg0rz950xywrjQ&cad=rja Second link is http://homepages.ius.edu/rwisman/C455/html/notes/Chapter4/RecursionTree.htm – bsoundra Nov 02 '11 at 22:01
