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}

  • 2
    $\begingroup$ @Evil i am sorry, i have corrected the post, please let me know if i need to change any thing in it. $\endgroup$ – 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.

  • $\begingroup$ 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 $\endgroup$ – Naveen Jul 1 '19 at 13:33
  • $\begingroup$ @Naveen if any amount of work divided in two on each level, how much levels do you have if total amount is $n$? $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.