|
|
Dear Jose Carlos Santos,
Can I ask for a quick additional hint since the last one really helped?
Suppose that a sequence is defined by the following recurrence
relation:
a_{n}=a_{n-1} + a_{n-2} + a_{n-3}
and you are given some initial values a_{0}, a_{1} and a_{2}
Also suppose that a recursive algorithm uses the recurrence relation
three times to evaluate a_{n-1}, a_{n-2} and a_{n-3} and then adds the
resulting values to obtain a_{n}.
Would it be possible to have a hint as to how I would show that the
total number of times t_{i} that a_{n-i} is evaluated satisfies:
t_{i}=t_{i-1} + t_{i-2} + t_{i-3}
with t_{0}=t_{1}=1 and t_{2}=2.
Sorry that it is quite long.
I am a second year undergraduate student and algorithms is not my
preferred field!
Any help would be MUCH appreciated.
Thanks,
Alex
|
|