patternMinor
Solving the recurrence T(n) = 3T(n-2) with iterative method
Viewed 0 times
solvingthemethoditerativewithrecurrence
Problem
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?
$$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?
Solution
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})$.
The correct answer thus is $T(n) = O(3^{n/2}) = O(\sqrt{3^n})$.
Context
StackExchange Computer Science Q#24290, answer score: 7
Revisions (0)
No revisions yet.