1
$\begingroup$

The solution is to find the upper and lower bounds from:

2T(n-2) < T(n) < 2T(n-1) + 10

So I have to find 

T(n) > 2T(n-2)

and

T(n) < 2T(n-1) + 10

My question about this solution method is not how to solve those recurrence relations. It's about why this method can be used in the first place. I thought solving a recurrence relation is about finding the precise runtime and not about finding the approximate runtime between its lower and upper bounds. Is there a way to solve the recurrence relation without using this method and finding out the precise runtime?

|cite|improve this question|||||
$\endgroup$
  • 2
    $\begingroup$ You mention runtime, but I don’t see any code here. A recurrence can represent things beyond runtime. For example, the amount of money in your bank satisfies a recurrence. $\endgroup$ – Yuval Filmus Mar 12 '19 at 23:02
  • 1
    $\begingroup$ Try $S(n) = T(n) + 10$. $\endgroup$ – Yuval Filmus Mar 12 '19 at 23:03
  • $\begingroup$ $T(n)\sim c\left(\dfrac{1+\sqrt5}2\right)^n$ for some constant $c$ (assuming $T(n)\ge0$). $\endgroup$ – John L. Mar 13 '19 at 21:51
  • $\begingroup$ If you want to understand why the above comment is true, look into the golden ratio, and how it relates to the fibonacci sequence $\endgroup$ – dustinroepsch Mar 14 '19 at 17:09
4
$\begingroup$

The goal of a recurrence relation is to make a complicated problem easier to think about, which is very general. It allows us to express a function in terms of itself, but still reason about what the value of the function for an input is.

Sometimes you care about the exact value of the function, in which case you'd prefer to rewrite it in an exactly equivalent way (or just plug in a number and follow the recursion chain until you have your answer).

Other times, you're just worried about the extreme "if my worst enemy plugged a value into this function, what would it do?" case.

Rewriting the equation as an inequality let's us remove an entire recursive call of the function, which makes doing substitutions to figure out an easier to reason about form of the function a more achievable goal.

So yes, $T(N) = T(N-1) + T(N-2) + 10$, may exactly describe the run time of your program, or the amount of money in my bank account after $N$ days (I wish), but we don't care about that precision, because $T(N) < 2T(N-1) + 10$ is an upperbound, and we just want to know that our program will finish before the heat death of the universe, or that I have enough money in my bank account for dinner.

Note the benefit here. Perhaps because your algorithm had a recursive nature to it, it might have been really easy to come up with the $T(N) = T(N-1) + T(N-2) + 10$ description of the run time. Easy to come up with, but hard to think about what the function actually means. So now that we have this building block, we come up with an upper bound (that we know is true), but has less recursion (which our brains don't like). This is nice on its own, but it also let's us continue to expand the recursive definition until we understand the underlying pattern, and can remove the recursion completely.

|cite|improve this answer|||||
$\endgroup$
2
$\begingroup$

I thought solving a recurrence relation is about finding the precise runtime and not about finding the approximate runtime between its lower and upper bounds.

No, solving a recurrence is solving a recurrence. It's unfortunate that students often get the impression that recurrence relations are necessarily about running times. Wouldn't it be bizarre if a physicist believed that multiplication is "calculating a force" because they'd learnt that $F=ma$?

And why should solutions always be exact? Maybe you need it exact, maybe you don't. Suppose you want to fill your kids' circular paddling pool with water, and it's $1.5\,\mathrm{m}$ across and $20\,\mathrm{cm}$ deep. How much water do you need? Are you going to insist that the answer is $225\pi/2$ litres or is "between $353$ and $354$" litres good enough? Or even just "about $350$ litres"?

|cite|improve this answer|||||
$\endgroup$
1
$\begingroup$

Given the recurrence

$\qquad\displaystyle T(n) = T(n-1) + T(n-2) + 10$

with reasonable initial conditions, e.g. $T(0) = 1$ and $T(1) = 2$, it is easy to see that $T$ is strictly increasing. (I leave a proof as exercise; use that $T(n) \geq 0$ for all $n$ here.) That means that $T(n-1) > T(n-2)$ and therewith, indeed,

$\qquad\displaystyle 2T(n-2) + 10 \leq T(n) \leq 2T(n-1) + 10$

for $n \geq 2$. The more you learn about $T(n-1) - T(n-2)$, the tighter you can make these bounds!

As a consequence, with

$\qquad\displaystyle T_l(n) = 2T_l(n-2) + 10$ and

$\qquad\displaystyle T_u(n) = 2T_u(n-1) + 10$

we obtain that

$\qquad\displaystyle T_l(n) \leq T(n) \leq T_u(n)$.

Solve those two simpler recurrences (again, details left as excercise) and you obtain that

$\qquad\displaystyle T \in \Omega(\sqrt{2}^n) \cap O(2^n)$,

where exact figures instead of Landau bounds are quite achievable with basic techniques.

|cite|improve this answer|||||
$\endgroup$
0
$\begingroup$

By substituting $F(n)=T(n)+10$, we obtain exactly the relation of the Fibonacci series, which grows as $O(e^n)$.

|cite|improve this answer|||||
$\endgroup$
  • 1
    $\begingroup$ The upper bound can be improved significantly. $\endgroup$ – Yuval Filmus Mar 13 '19 at 17:18

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.