0
$\begingroup$

I want to be able to find closed form runtime solution for recursive insertion sort which looks something like this

$$T(n)=\begin{cases} 1 &\text{if }n=1,\\ T(n−1)+3n &\text{if }n>1. \end{cases}$$

However, I am confused about how to plot a tree. I know how to find runtime using tree if problem is divided into half. But here problem is just reduced by one. How does it work?

$\endgroup$
  • $\begingroup$ A tree node that only has one child will still constitute a tree. Consider the fact that a linked list is also a tree. So instead of having 2 subproblems here, you only have 1, of size $n-1$. $\endgroup$ – ryan Apr 15 '19 at 16:12
2
$\begingroup$

Expanding the recursion, we get $$ \begin{align*} T(n) &= 3n + T(n-1) \\ &= 3n + 3(n-1) + T(n-2) \\ &= 3n + 3(n-1) + 3(n-2) + T(n-3) \\ &= \cdots \\ &= 3n + 3(n-1) + 3(n-2) + \cdots + 3(2) + T(1) \\ &= 3n + 3(n-1) + 3(n-2) + \cdots + 3(2) + 1. \end{align*} $$ Therefore $$ T(n) = 1 + \sum_{m=2}^n 3m. $$ You take it from here.

$\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.