Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Newsgroups | comp.theory |
| Subject | Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics |
| Date | 2021-09-20 21:38 +0100 |
| Organization | A noiseless patient Spider |
| Message-ID | <87zgs756fi.fsf@bsb.me.uk> (permalink) |
| References | <a7c2345d-e3ab-4296-8b1b-877212aa8c7dn@googlegroups.com> |
Charlie-Boo <shymathguy@gmail.com> writes: > A closed form i.e. O(1) is the Holy Grail of Algorithmics. Closed forms are rarely O(1). First, O(1) depends on some measure. In comp.theory it's reasonable to expect you mean O(1) steps of a Turing machine. Secondly, O(1) is about an algorithm, so the "cost" of evaluating a closed form depends on how good an algorithm you have. I.e. I can't show you a wrong simply by showing an O(n) algorithm for some closed form, because there might be a better one I have not thought of. Third, the order of an algorithm can depend on the encoding of the "inputs" and the "outputs" so I'd have to cover every conceivable encoding as well. I don't have the time or the inclination to do that, so here's a challenge... Given the simple function f(n) = n+1, do you think there is an encoding for n (and for the result) such that some TM M can compute f(n) in O(1)? The long and the short of it is that I don't think you meant to say what you said. That O(1) means something to you which is not the usual technical meaning. -- Ben.
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