1
$\begingroup$

I am trying to solve the recurrence

$T\left(n\right)\:=\:3T\left(n-1\right)\:+\:3n^2$

I tried method I saw but I do not fully understand which looks like:

$T\left(n-1\right)\:=\:3T\left(n-2\right)\:+\:3\left(n-1\right)^2$

$T\left(n\right)\:=\:3\left[3T\left(n-2\right)\:+\:3\left(n-1\right)^2\right]\:+\:3n^2$

$T\left(n\right)\:=\:3\left[3(3T\left(n−3\right)+3\left(n−2\right)^2)\:+\:3\left(n-1\right)^2\right]\:+\:3n^2$

But I am not sure if this is the right way and how do I continue.

$\endgroup$

3 Answers 3

1
$\begingroup$

Let $S(n) = T(n)/3^n$. Then $$ S(n) = \frac{T(n)}{3^n} = \frac{T(n-1)}{3^{n-1}} + \frac{3n^2}{3^n} = S(n-1) + \frac{n^2}{3^{n-1}}. $$ You take it from here.

$\endgroup$
4
  • $\begingroup$ I am not sure how to take it from here $\endgroup$
    – LoveYourz
    Commented Feb 21, 2022 at 14:12
  • 1
    $\begingroup$ I'm sorry, you'll have to work it out. Try harder. $\endgroup$ Commented Feb 21, 2022 at 17:58
  • $\begingroup$ It looks almost the same as the problem before for me in terms of what should I do with this kind of equations, so I don't even know how try try harder, what should I look at $\endgroup$
    – LoveYourz
    Commented Feb 22, 2022 at 7:09
  • $\begingroup$ You can get an explicit formula for $S(n)$ by unrolling the recurrence. You get a sum, which you can either estimate as $O(1)$, as in Steven's answer, or compute exactly, say using Wolfram alpha. $\endgroup$ Commented Feb 22, 2022 at 8:11
1
$\begingroup$

You can continue unrolling the recurrence until you see the pattern, and you are able to write a general formula. Then instantiate it in a way that results in writing $T(n)$ as a function of the base case (which I'm going to assume being $T(1)=1$).

$$ \begin{align*} T(n) &= 3 \cdot T(n-1)+ 3n^2 \\ T(n) &= 3^2 \cdot T(n-2) + 3^2(n-1)^2 + 3n^2 \\ T(n) &= 3^3 \cdot T(n-3) + 3^3 (n-2)^2+ 3^2(n-1)^2 + 3n^2 \\ & \vdots \\ T(n) &= 3^i \cdot T(n-i) + \sum_{j=1}^{i} 3^j (n-j+1)^2. \tag{*} \end{align*} $$

Therefore, choosing $i=n-1$: $$ T(n) = 3^{n-1} \cdot T(1) + \sum_{j=1}^{n-1} 3^j (n-j+1)^2 = 3^{n-1} + 3^{n+1} \sum_{j=2}^{n} 3^{-j} \cdot j^2. $$

Since $\sum_{j=2}^{n} 3^{-j} \cdot j^2 \le \sum_{j=2}^{\infty} 3^{-j} \cdot j^2$, and the latter series is convergent, you have $T(n)=\Theta(3^n)$.

Notice that the above argument involves some "magic" dots, where you are claiming that after unrolling the recursion $i$ times you get $(*)$. To get a formal proof you need to proceed by induction.

$\endgroup$
0
$\begingroup$

Now, Initial Conditions of Recurrence Relation are not given.

Still, We can use Master Theorem to find asymptotic bound of given recurrence relation without any initial condition(s).

(For Solving the Recurrence Relation, we need initial conditions, which are not mentioned in problem)

If a Recurrence Relation is of the Form

$$T(n)=aT\big(n-b\big)+{f(n)}$$

Then, as per Master Theorem, we have Three Conditions depending on value of $a$

  • If $a=1$
    Answer is $O(nf(n))$

  • If $a>1$
    Answer is $O(a^{\frac{n}{b}}f(n))$

  • If $a<1$
    Answer is $O(f(n))$

In any problem, our main motive is to find $a, f(n)$ and $b$. Moreover we can replace $f(n)$ by it's asymptotic equivalent.

In Given Problem

  • $a=3$
  • $b=1$
  • $f(n)=n^2$

Now, $a>1$ Therefore, Answer is $O(3^{n}n^2)$

$$O(3^{n}n^2)$$

$\endgroup$
8
  • $\begingroup$ The conditions you state cannot possibly be true. Consider $T(n)=T(n-1) + 2^n$, with $T(1)=2$. Then $a=1$ and $b=1$ but we have $T(n) = \sum_{i=1}^n 2^i = 2^{i+1} - 2 \not\in \Theta(n 2^n)$. $\endgroup$
    – Steven
    Commented Feb 21, 2022 at 16:20
  • $\begingroup$ @Steven, The summation will be equal to $2^{n+1}-2$, which does belongs to $O(n2^n)$. The $\Theta$ has been replaced by $O$ $\endgroup$ Commented Feb 21, 2022 at 17:06
  • $\begingroup$ @RohitSingh How does it appeal when $f\left(n\right)\:=\:logn$ ? $\endgroup$
    – LoveYourz
    Commented Feb 22, 2022 at 9:06
  • $\begingroup$ It will be $O(3^{n}logn)$. Please note that $f(n)$ need not to be a polynomial function. $\endgroup$ Commented Feb 22, 2022 at 14:45
  • $\begingroup$ I am afraid I didn't get what you meant by not to be a polynomial function. In first question for example, is $3n^2$ not a polynom? for a=2, b=0, c=0 for example @RohitSingh $\endgroup$
    – LoveYourz
    Commented Feb 22, 2022 at 15:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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