Problem Detail: 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?
Asked By : wpp
Answered By : FrankW
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})$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/24290
