Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.