How do we guess the recurrence relation from the given equation

Question

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) & \leq 2(c\lfloor n / 2\rfloor \lg (\lfloor n / 2\rfloor))+n \\ & \leq c n \lg (n / 2)+n \\ &=c n \lg n-c n \lg 2+n \\ &=c n \lg n-c n+n \\ & \leq c n \lg n \end{aligned}

Answer 1

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.

Answer 2

The guess $O(n^2)$ also works: $$ T(n) \leq 2c\lfloor n/2\rfloor^2 + n \leq \frac{c}{2} n^2 + n \leq cn^2, $$ as long as $c \geq 2$.

The author did not guess the answer. Presumably the author already knew the answer.

In practice, for most recurrences you would encounter one of the following methods will work:

• Open up the recurrence (also known as repeated substitution).
• Appeal to a standard result such as the master theorem.
• Use a computer experiment (could be deceiving).

In this case, the recurrence is so well-known and commonplace that the author must have seen it worked out somewhere. It can also be "solved" (i.e., the asymptotic behavior of $T(n)$ determined) using the master theorem, which is how you could do it.