How do we guess the recurrence relation from the given equation In this book introduction to algorithms , i have been reading about a method named substitution method to solve the recurrence, the recurrence equation is 
\begin{equation}
T(n)=2 T(\lfloor n / 2\rfloor)+n
\end{equation}

the author guessed the solution was $O(n \log n)$ and proved it below, my question is how to make the guess? I wanted to know why it cant be $O(n^2)$? How do you guess them correctly at first?

\begin{aligned} T(n) &amp; \leq 2(c\lfloor n / 2\rfloor \lg (\lfloor n / 2\rfloor))+n \\ &amp; \leq c n \lg (n / 2)+n \\ &amp;=c n \lg n-c n \lg 2+n \\ &amp;=c n \lg n-c n+n \\ &amp; \leq c n \lg n \end{aligned}
To guess simple recurrences most useful step is to study basic intuition beyond so-called master theorem that looks at any recursion as if it is implicit tree.

Your case is admissible for it and thus easy: on each step you have half of task (peek one branch down in tree), and $O(n)$ work. Multiply tree height and amount of work on each step and you will get your guess. But you will probably never guess any inadmissible case.