2
$\begingroup$

I have a funcion $T: \mathbb{N}\to\mathbb{N}$ defined as:

$$T(n)=\begin{cases} 6 &\text{ if } n=0,\\ T(n-1) + 6n + 6 &\text{otherwise.} \end{cases}$$

How can I apply the Master Theorem to this problem? I have only seen the M.T. in one of these two formats:

$$T(n) = aT(n/b) + f (n)$$ $$T(n) = aT(n/b) + \Theta(n^c)$$

So I'm wondering how to transform the $T(n-1)$ to something usable. Is it even possible to apply the theorem to this kind of problem?

$\endgroup$
4
$\begingroup$

Not every recurrence falls within the bounds on the master theorem. Your recurrence is an example. However, by unrolling your recurrence, we can come up with an explicit formula: $$ T(n) = 6(n+1) + T(n-1) = 6(n+1) + 6n + T(n-2) = \cdots = \\ 6(n+1) + 6n + \cdots + 6\cdot 2 + T(0) = \\ 6(n+1) + 6n + \cdots + 6\cdot 2 + 6\cdot 1 = \\ 6 \sum_{m=1}^{n+1} m = 6\frac{(n+2)(n+1)}{2} = 3(n+2)(n+1). $$

$\endgroup$
0
$\begingroup$

The master theorem simply doesn't apply in this case. There is no constant $b$ such that $n-1=n/b$ for all $n$. You must use some other technique to solve the recurrence.

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