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 '15 at 6:53
  • $\begingroup$ I don't understand your last paragraph: I can't parse it as a sentence. $\endgroup$ – David Richerby Mar 6 '15 at 8:51

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$ – David Richerby Mar 6 '15 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$ – James Combs Mar 6 '15 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$ – James Combs Mar 6 '15 at 17:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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