Supposing I write an algorithm that results into this kind of recurrence relation

$$\left\{ \begin{array}{ll} T(0)=T(1)=1 \\ T(n)=T\left(\lfloor n/2 \rfloor \right)+T\left(\lceil n/2 \rceil\right)+c_1n+c_2 \end{array} \right.$$

This kind of algorithm looks like it is of $O(n\log(n))$ but how can I solve this recurrence relation to find its complexity?

  • $\begingroup$ can you continue it and express $T(n/2)$ left part i meant $\endgroup$ – dato datuashvili Apr 5 '13 at 20:34
  • 1
    $\begingroup$ i don't get what you're saying. $\endgroup$ – user31280 Apr 5 '13 at 20:42
  • 1
    $\begingroup$ You could verify it for 2-powers first and then try to reduce the general case to this special case. $\endgroup$ – Hans Giebenrath Apr 6 '13 at 6:32
  • $\begingroup$ @HansGiebenrath great idea! thanks $\endgroup$ – user31280 Apr 6 '13 at 14:18

Your Answer

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