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 $$$$T(n)=2 T(\lfloor n / 2\rfloor)+n$$$$

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}

• @Evil i am sorry, i have corrected the post, please let me know if i need to change any thing in it. – Naveen Jul 1 '19 at 4:46

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.

• how do i peek one branch in a tree? the equation is given like 2𝑇(⌊𝑛/2⌋)+𝑛 but from that thing i can only figure out each node gets divided in to two at each step – Naveen Jul 1 '19 at 13:33
• @Naveen if any amount of work divided in two on each level, how much levels do you have if total amount is $n$? – Konstantin Vladimirov Jul 1 '19 at 15:31

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.