2
$\begingroup$

So, this is how I solved

$\displaystyle T(n-1) \approx{} T(n-2) $

$\displaystyle T(n) = T(n-1)^2 $

Add log in both sides

$\displaystyle log(T(n)) = 2log(T(n-1)) $

$\displaystyle Let\:\: log(T(n)) = S(n) $

$\displaystyle S(n) = 2(S(n-1)) $

We know that from Fibonacci series

$\displaystyle S(n) = O(2^n) $

$\displaystyle log(T(n)) = O(2^n) $

$\displaystyle (T(n)) = O(2^{2^n}) $

Ok, so where did I go wrong here??

$\endgroup$
  • 1
    $\begingroup$ 1) You seem to be after solving a recurrence for function $T$, not analysing a recursive algorithm called T. 2) You're using $=$, $\approx$, and $= O$ a little willy nilly. Try deriving sandwich recurrences, i.e. $T_l(n) \leq T(n) \leq T_u(n)$, given by recurrences you can solve. If $T_l \in \Theta(T_u)$, you've won. $\endgroup$ – Raphael Feb 20 at 20:21
  • 1
    $\begingroup$ Be very careful using this "log on both sides" thing. It does not always work! See our reference questions here and here for related reading. $\endgroup$ – Raphael Feb 20 at 20:23
  • 2
    $\begingroup$ Taking logarithm on both sides immediately would have been so simple and led directly to the result. $\endgroup$ – gnasher729 Feb 20 at 20:58
2
$\begingroup$

What is wrong?

So, this is how I solved
$T(n-1) \approx{} T(n-2)$
$T(n) = T(n-1)^2$

An equality is the most precise and most powerful entity in the world. Please treat it with due respect.

Let me show how wrong it is if you use approximation liberally with equalities. If your argument above is sound, we can also do the following.
$\quad T(n) \approx{} T(n-1)$
$\quad T(n-1) = T(n-1)*T(n-2)$
$\quad T(n-2) = 1$ if $T(n-1)$ is not 0.
So $T(n)$ must be 0 or 1 from time to time . That is obviously false, however. For example, we can let $T(1)=T(2)=2$.


What to do?

What you can do is, as gnasher729 suggested, "taking logarithm on both sides immediately", assuming $T(1)>0$ and $T(2)>0$, which can be assume generally when we are analyzing recurrence relations in computer science.

You can also, of course, dive into analysis by cases when $T(1)$ and $T(2)$ might be 0 or even negative.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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