Re: closed form for T(n) = c^n + T(n-1)
- From: Daniel Cer <cer@xxxxxxxxxxxxxxxx>
- Date: Sun, 12 Feb 2006 08:16:42 +0000
T(0) = a
T(n) = c^n + T(n-1)
<snip>
That doesn't seem right. I make it T(n) = 2^(n+1) - 2 + a for c = 2,
and T(n) = (c^(n+1)-1)/(c-1) - 1 + a in general
Perhaps you meant the recurrence relation to be T(n) = a*c^n + T(n-1) ?
In that case it's T(n) = a*(c^(n+1)-1)/(c-1)
which gives T(n) = a*(2^(n+1)-1) (same as your latest) for c = 2
Thanks, David. The recurrence T(n) = a*c^n + T(n-1) was what I had in
mind. Apologies for the multiple errors in the original post.
-Dan
.
- Follow-Ups:
- Re: closed form for T(n) = c^n + T(n-1)
- From: beelzebub
- Re: closed form for T(n) = c^n + T(n-1)
- References:
- closed form for T(n) = c^n + T(n-1)
- From: Daniel Cer
- Re: closed form for T(n) = c^n + T(n-1)
- From: Daniel Cer
- Re: closed form for T(n) = c^n + T(n-1)
- From: David Kinny
- closed form for T(n) = c^n + T(n-1)
- Prev by Date: Re: help proving decidability of a set
- Next by Date: Ambuguity of CFG
- Previous by thread: Re: closed form for T(n) = c^n + T(n-1)
- Next by thread: Re: closed form for T(n) = c^n + T(n-1)
- Index(es):
Relevant Pages
|
