2
$\begingroup$

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}

$\endgroup$
  • 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
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\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
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

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.