7
$\begingroup$

It's been a while since I had to solve a recurrence and I wanted to make sure I understood the iterative method of solving these problems. Given:

$$T(n) = 3T(n-2)$$

My first step was to iteratively substitute terms to arrive at a general form:

$$T(n-2) = 3T(n-2 -2) = 3T(n-4)$$ $$T(n) = 3 *3T(n-4)$$

leading to the general form:

$$ T(n) = 3^k T(n-2k) $$

Now I solve $n-2k = 1$ for $k$, which is the point where the recurrence stops (where $T(1)$) and insert that value ($n/2 - 1/2 = k$) into the general form:

$$T(n) = 3^{n/2-1/2}$$ $$T(n) = O(3^n)$$

I'm not sure about that last step:

I would just "argue" that as $n \to \infty$ one can ignore $-1/2$ and $n/2 \to n$ ? Is that assumption correct?

$\endgroup$
1
  • $\begingroup$ You can drop the $-1/2$ upfront, as the $O$ notation absorbs constant factors. But $3^n$ is not proportional to $3^{n/2}$. $\endgroup$
    – user16034
    Mar 14, 2023 at 7:50

3 Answers 3

7
$\begingroup$

Note that $3^{n/2-1/2} = \frac{1}{\sqrt{3}} 3^{n/2} = \frac 1{\sqrt{3}} \sqrt{3^n}$. So the $-\frac 12$ indeed becomes a constant factor that is absorbed by the $O()$, but $\frac n2$ in the exponent changes the base and changing the base changes the $O$-class.

The correct answer thus is $T(n) = O(3^{n/2}) = O(\sqrt{3^n})$.

$\endgroup$
1
  • $\begingroup$ Thank you both @FrankW and @Jared! I marked this answer as correct because it contains an explanation (changing the base changes O-class). $\endgroup$
    – wpp
    May 1, 2014 at 11:36
6
$\begingroup$

Everything was correct up until the last step...you found:

$$ T(n) \propto 3^{\frac{n}{2}- \frac{1}{2}} = \left(3^{n - 1}\right)^{\frac{1}{2}} = \frac{1}{\sqrt{3}}\left(\sqrt{3}\right)^n $$

$\endgroup$
0
$\begingroup$

More rigorously:

First note that the recurrence only involves terms that are two units apart, so there will be a solution for the even $n$ and an independent one for the odd.

Let first $n:=2m$. We have

$$T(2m)=3T(2m-2)=3^2T(2m-2\cdot2)=\cdots3^mT(0)$$

or

$$T(n)=3^{n/2}T(0)=(3^{1/2})^nT(0)=\sqrt3^nT(0).$$ And similarly for odd $n$,

$$T(n)=\sqrt3^{n-1}T(1).$$

This is captured by

$$T(n)=\Theta(\sqrt3^n).$$

$\endgroup$

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.