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?

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

1 Answer 1


Think of it this way, you have a mathematically formal description of a recursive function. Which every function maps an element (or more than one element) To 1 element in the codomain.

What would T(0) be in terms of this functions as an input? It wouldn't change the time complexity.

  • $\begingroup$ 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? $\endgroup$ Mar 6, 2015 at 8:49
  • $\begingroup$ It seems to be a sentence fragment but isn't. I just happen to know the formal definition of a function being a computer science student, which I'd hope is pretty normal. T(0) is clearly the function here. The function is expressed in terms of itself. Being divided in each recurrence. OP said he/she have stopped the leavs of his/her tree at T(1). OP is wondering whether if he/she let the leaves go to T(0), if it would change the solution, assuming the solution he/she is looking for is the upper bound time complexity. $\endgroup$ Mar 6, 2015 at 17:51
  • $\begingroup$ Which it would not. It is just another recurrence of the function with 0 as its input. I'm not sure where OP wants to have that condition, but it will not change the time complexity he/she has analyzed. It is not dividing the problem further. $\endgroup$ Mar 6, 2015 at 17:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.