Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | Jeff Barnett <jbb@notatt.com> |
|---|---|
| Newsgroups | comp.theory |
| Subject | Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics |
| Date | 2021-09-20 11:05 -0600 |
| Organization | A noiseless patient Spider |
| Message-ID | <siaf08$1ft$1@dont-email.me> (permalink) |
| References | <a7c2345d-e3ab-4296-8b1b-877212aa8c7dn@googlegroups.com> |
On 9/20/2021 10:38 AM, Charlie-Boo wrote:
> A closed form i.e. O(1) is the Holy Grail of Algorithmics.
>
> Every problem is a recursive definition since running a program is evaluating a recursive definition.
>
> [Let INIT = Initial State. NEXTSTATE(state) = Iterate. HALTS(state)="Does state halt?" Then PROG(Input) is HALTS(Input)?Input:PROG(NEXTSTATE(Input)).]
>
> The Nth Fibonacci Number is a recursive definition but there is a closed form (e.g. wiki.)
>
> (The trick, however, is that iteration is replaced by exponentiation of a real number.)
>
> How far have people gotten in developing closed forms for recursive definitions starting with Fibonacci?
>
> Solving this 2-place function over N would be helpful (I will explain.)
>
> 2 5 34 1,597
> 8 55 2,584
> 144 6,765
> 46,368
>
> C-B
>
First things first. Evaluating a closed form is not necessarily O(1).
For example, 2^{2^{2^ ...... {2^n}}} is as much a closed form as is n^2.
If we are measuring computational cost, there is a non constant amount
of work to do depending on the size of n, the representation of n, and
the representation of the value. Further, the order of magnitude of the
work depends on algorithm and computing device.
I think what you meant to say is evaluating f(n) is O(1) if f(x) is a
constant for all x. Of course if your computation method must read x
even though it is not relevant, than the order of the work is O(|x|),
where |x| is the length of the string representing the value of x.
--
Jeff Barnett
Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Charlie-Boo <shymathguy@gmail.com> - 2021-09-20 09:38 -0700
Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Jeff Barnett <jbb@notatt.com> - 2021-09-20 11:05 -0600
Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Charlie-Boo <shymathguy@gmail.com> - 2021-09-20 11:43 -0700
Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Jeff Barnett <jbb@notatt.com> - 2021-09-20 14:01 -0600
Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Charlie-Boo <shymathguy@gmail.com> - 2021-09-24 16:41 -0700
Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Jeff Barnett <jbb@notatt.com> - 2021-09-24 20:46 -0600
Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-20 21:38 +0100
Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Charlie-Boo <shymathguy@gmail.com> - 2021-09-24 11:10 -0700
Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Charlie-Boo <shymathguy@gmail.com> - 2021-09-24 11:23 -0700
Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-24 21:40 +0100
Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Charlie-Boo <shymathguy@gmail.com> - 2021-09-24 16:45 -0700
Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-25 21:31 +0100
Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-09-26 10:26 -0700
Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-26 19:02 +0100
Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Charlie-Boo <shymathguy@gmail.com> - 2021-09-24 17:04 -0700
Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-25 21:35 +0100
csiph-web