# Problem with Understanding a Recursion Tree

Consider the recursion tree:

$T(p) = 3T(\frac{2p}{8}) + 2T(\frac{p}{8}) + O(p)$.

I determined that there are at most $1 + log_{4}\ p$ levels, because the longest simple path from root to leaf is $p \rightarrow \frac{2p}{8} \rightarrow \frac{4p}{16} \rightarrow \frac{8p}{32} \rightarrow\ ...$.

This means that the time complexity is $O(p\ log\ p)$.

Now, I stopped all my leaves in the above recursion tree have $T(1)$, but say I have the condition $T(0) + O(1)$. Does this change my solution somehow?

• There is no "time complexity" here, just a recurrence (class). – Raphael Mar 6 '15 at 6:53
• I don't understand your last paragraph: I can't parse it as a sentence. – David Richerby Mar 6 '15 at 8:51

• Welcome and thank you for posting but I can't understand what you're saying at all. What do you mean by "a mathematically formal description of a recursive function"? What other kind of description would there be? What do you mean by "Which every function maps..."? That seems to be a sentence fragment. Why are you trying to express $T(0)$ in terms of some function you've not defined? What wouldn't change the time complexity from what to what? – David Richerby Mar 6 '15 at 8:49