# Solving recurrence relation of algorithm complexity?

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?

• 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