Take the 2-minute tour ×
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.

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|improve this question
    
can you continue it and express $T(n/2)$ left part i meant –  dato datuashvili Apr 5 '13 at 20:34
1  
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

 
discard

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