Solving the big-Oh notation for $T(n) = 2 T(n/2) + O(n)$
It means "open" the recursion.

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

$$ \begin{align}
T(n) &amp;= 2T(n/2) + cn \\ 
&amp;= 2(2T(n/4) + cn/2) + cn\\ 
&amp;= 2  (2  (2T(n/8) + cn/4) + cn/2) + cn\\
&amp; \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) &lt;= n*logn + n

Base:
T(1) = 1 (assumption)

Assumption: the claim is correct for all k &lt; n.
Proof:

T(n) = 2T(n/2) + n = (assumption) &lt;= 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