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

Groups > comp.programming > #7662

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

Show key headers only | View raw

Daniel Bastos <dbastos@toledo.com> writes:

> Here's an argument to prove that 2^O(lg n) is a polynomial.

You are tripping up over your terminology.  2^O(lg n) is a set of
functions ans do can't be polynomial.  You can't even say that the
member function are polynomials.  What you can say (if it's true) is
that the functions in it are asymptotically bounded above by a
polynomial.  In other words, you are trying to prove that

  if f(n) in 2^O(lg n) the there exists k such that f(n) in O(n^k).

> Fact.  f(n) in 2^O(lg n) is a polynomial.

This is not going to be a theorem!  f(n) might be bounded above by some
polynomial (for sufficiently large n) but it is not guaranteed to be one
itself.

> Proof.  By definition, f(n) in 2^O(lg n) means that there's a real c > 0
> and natural n(0) such that for all n >= n(0)
>
>   0 <= f < 2^{c lg n} = 2^{lg(n^c)} = n^c
>
> QED.
>
> It's hard for me to say what's precisely wrong here, but I disagree with
> the result.  I think there are functions in 2^O(lg n) which are not
> polynomials.  For example,
>
>   2^{lg(lg n)} n^c is in 2^O(lg n)
>
> because 2^{lg(lg n)} n^c < 2^{c lg n} for c = 1 and n(0) = 2.  But
> clearly 2^{lg(lg n)} n^c is not a polynomial because lg(lg n) is not a
> constant.

Sure, but f in 2^O(lg n) won't ever mean that f is a polynomial, only
that is it bounded above by one.

> What's wrong with that argument?  Or where am I wrong?  Thank you.

-- 
Ben.

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