How to determine the height of a recursion tree from a recurrence relation?

recursion tree computer-science recurrence proof
Chris picture Chris · Aug 28, 2009 · Viewed 30.5k times · Source

How does one go about determining the height of a recursion tree, built when dealing with recurrence run-times? How does it differ from determining the height of a regular tree?

alt text http://homepages.ius.edu/rwisman/C455/html/notes/Chapter4/ch4-9.gif

edit: sorry, i meant to add how to get the height of the recursion tree from the recurrence relation.

Answer

ejel picture ejel · Sep 25, 2009

If recurrence is in the form of T(n) = aT(n/b) + f(n) then the depth of the tree is log base b of n.

For example, 2T(n/2) + n recurrence would have tree of depth lg(n) (log base 2 of n).

Related questions

What is the most efficient/elegant way to parse a flat table into a tree?

Assume you have a flat table that stores an ordered tree hierarchy: Id Name ParentId Order 1 'Node 1' 0 10 2 'Node 1.1' 1 10 3 'Node 2' 0 20 4 'Node 1.1.1' 2 10 5 'Node 2.1' 3 10 6 'Node 1.2' 1 20 Here's a diagram, where we have [id] Name. Root node 0 is fictional. [0] …

Read More
create array tree from array list

i have a list like this: array( array(id=>100, parentid=>0, name=>'a'), array(id=>101, parentid=>100, name=>'a'), array(id=>102, parentid=>101, name=>'a'), array(id=>103, parentid=>101, name=>'a'), ) but …

Read More
PHP tree structure for categories and sub categories without looping a query

I'm trying to create a list of categories with any number of sub categories, where sub categories can also has their own sub categories. I have selected all categories from the Mysql db, the cats are in a standard associate …

Read More