Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #7635

Re: on 2^O(lg n) being a polynomial

Show all headers | View raw

On 2017-03-25, Daniel Bastos <dbastos@toledo.com> wrote:
> Here's an argument to prove that 2^O(lg n) is a polynomial.

You have to define precisely what the syntax means when the O notation
is used as an exponent.

Perhaps we can frame the O notation as denoting a *set* of functions.
The O(lg n) expression can denote the set of all functions f(n)
which we say "are" O(lg n). Thereby, we disembody it and allow it
to function as a term.

Then raising an expression to the power of O(...) is what?

Perhaps a mapping: 2^O(expr) might mean that 2 is raised to every
element of the set O(expr), resulting in a new set.

Thus, 2 raised to every function that is O(lg n).

Then what do we mean by saying this "is a polynomial"?

Probably that every element of the set is a polynomial: a sum of
the integral powers of n from zero up to some finite order, each
multiplied by a coefficient.

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

on 2^O(lg n) being a polynomial Daniel Bastos <dbastos@toledo.com> - 2017-03-24 22:25 -0300
  Re: on 2^O(lg n) being a polynomial Kaz Kylheku <336-986-7787@kylheku.com> - 2017-03-25 02:39 +0000
  Re: on 2^O(lg n) being a polynomial Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-28 14:25 +0100
    Re: on 2^O(lg n) being a polynomial Kaz Kylheku <336-986-7787@kylheku.com> - 2017-03-28 17:45 +0000
    Re: on 2^O(lg n) being a polynomial Daniel Bastos <dbastos@toledo.com> - 2017-03-28 20:28 -0300
      Re: on 2^O(lg n) being a polynomial Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-29 14:12 +0100

csiph-web