Tell me more ×
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.
up vote 2 down vote favorite
1

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 Apr 5 at 20:34
1  
i don't get what you're saying. – F'Ola Yinka Apr 5 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 at 6:32
@HansGiebenrath great idea! thanks – F'Ola Yinka Apr 6 at 14:18

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.