0
$\begingroup$

I've been learning master theorem in school now and have learnt how to apply it to a number of recurrence relations. However one of my assignments has the following recurrence relation:

T(n) = T(n-2) + n^2

Am I wrong in thinking that I cannot apply Master Theorem to this equation? If it can be applied, I am unsure how, as the variable T(n-2) gives no value for "b" which would usually be used to solve with master theorem.

If it can be solved with Master Theorem, how would it be solved? If it cannot be, how would one go about solving this specific recurrence relation?

Thank you in advance for any help and clarification!

Improve this question
$\endgroup$
1
  • 4
    $\begingroup$ Correct: the master theorem does not apply because the recurrence is not of the form $T(n) = aT(n/b) + f(n)$. For how to solve it, see our reference question. I recommend just expanding a few terms of the sum and seeing what happens. $\endgroup$
    – David Richerby
    Jun 24, 2016 at 23:55

4 Answers 4

Reset to default
3
$\begingroup$

Think about what the derivative of T is. If the difference between T (n) and T (n-2) is $n^2$ then the derivative T' (n) is about $n^2 / 2$ and T (n) is about $2/3 · n^3$.

Improve this answer
$\endgroup$
2
$\begingroup$

Don't use the Master theorem for this recurrence. Instead, use guess-and-prove, expand a few times and spot the pattern, or express it as a summation.

Improve this answer
$\endgroup$
1
$\begingroup$

If in the form:

$T(n) = aT(n-b)+f(n) ,\hspace{0.5cm} if \hspace{0.5cm}n>1,\hspace{0.5cm}a>0,\hspace{0.5cm}b>0,\hspace{0.5cm}k>=0$

and if $f(n)$ is $O(n^k)$ then

$T(n)=O(n^k) \hspace{0.5cm} if \hspace{0.5cm} a<1$

$T(n)=O(n^{k+1}) \hspace{0.5cm} if \hspace{0.5cm} a=1$

$T(n)=O(n^k.a^{n/b}) \hspace{0.5cm} if \hspace{0.5cm} a>1$

Improve this answer
$\endgroup$
2
  • $\begingroup$ 1) Citation or proof needed. 2) Why not more precise solutions? $\Theta$s should be easy, but we really want explicit, precise solutions here. $\endgroup$
    – Raphael ♦
    Jun 26, 2016 at 0:43
  • $\begingroup$ In expanded form, this may be suitable for this question or even the reference question. $\endgroup$
    – Raphael ♦
    Jun 26, 2016 at 0:45
-1
$\begingroup$

This: Solving Recurrence Relations 'Chip & Conquer' helped me solve the relation.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Please don't use the 'answer' box to comment on other answers or discuss the topic. The 'answer' box should be reserved solely for material that answers the question that was asked. (You can thank others by accepting the answer that was most helpful to you.) It looks like the second sentence is trying to answer the question, but we don't want link-only answers. We don't want to be just a link farm: we ask that you summarize the main ideas from that link, so that this will remain useful to others even if that link stops working. Thank you! $\endgroup$
    – D.W. ♦
    Jun 25, 2016 at 3:47
  • $\begingroup$ Understood. Sorry I'm pretty new to StackExchange, so I will definitely take note of these in the future! $\endgroup$
    – keenns
    Jun 25, 2016 at 22:10

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