Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Possible Duplicate:
Solving or approximating recurrence relations for sequences of numbers

I know that the solution for $T(n) = 2 T(n/2) + O(n)$ is $ T(n) = O(n \log(n))$

But how do you get to that point? I don't understand when it says put t into the equation repeatedly until it drops out...

Any help?

share|improve this question
    
@hd1 It may not be easy to do after the fact, but this knowledge does often help you make decisions before creating a first implementation. If you've learned your algorithmic theory well, it often doesn't take much extra time to deduce the complexities of different solutions (mostly a few seconds in your head). In a CPU-limited program, this can possibly save you from having to start over and find a whole new solution, after the fact. Of course, you also have to consider whether your data is big enough for the abstractions of the Big O notation to be valid. –  Agentlien Nov 23 '12 at 9:26
    
see also here –  A.Schulz Nov 23 '12 at 13:26
    
read about master theorem en.wikipedia.org/wiki/Master_theorem it is the fastest to calculate these kind of complexity –  Alexandros Mouzakidis Nov 23 '12 at 22:17
    
Since this question is completely answered by the one A.Schulz linked, I close this as a duplicate. If you face specific problems applying what you find there, please edit your question accordingly and flag for reopening. –  Raphael Nov 23 '12 at 22:42
add comment

migrated from stackoverflow.com Nov 23 '12 at 13:03

This question came from our site for professional and enthusiast programmers.

marked as duplicate by Raphael Nov 23 '12 at 22:41

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1 Answer

It means "open" the recursion.

For simplicity - denote $O(n)$ as $c\cdot n$:

$$ \begin{align} T(n) &= 2T(n/2) + cn \\ &= 2(2T(n/4) + cn/2) + cn\\ &= 2 (2 (2T(n/8) + cn/4) + cn/2) + cn\\ & \vdots \end{align}$$

It might give you intuition, but it is NOT a proof. To prove it, you will need mathematical induction or the master theorem.


Proving with induction (assuming O(n) component is n for simplicity):

Claim: T(n) <= n*logn + n

Base:
T(1) = 1 (assumption)
Assumption: the claim is correct for all k < n.
Proof:

T(n) = 2T(n/2) + n = (assumption) <= 2* (n/2 * log(n/2) + n/2) + n
     = n*log(n/2) + 2n = n*(log(n)-log(2)) + 2n = (assuming base 2 for log)
     = n*(log(n) -1 ) + 2n = nlogn -n + 2n = n*logn +n

QED

share|improve this answer
    
How would you prove with master theorem? –  user1846486 Nov 23 '12 at 9:25
    
@user1846486 just apply the formula. –  UmNyobe Nov 23 '12 at 9:26
    
what is the master theorem formula? –  user1846486 Nov 23 '12 at 9:28
1  
just google it :D –  UmNyobe Nov 23 '12 at 9:28
1  
Let me take it back—I think I just explained why instructors tell you this isn't a proof. It's because it's too hard to teach people how to do this properly in introductory algorithms courses. –  Peter Shor Nov 23 '12 at 14:04
show 7 more comments