Path: csiph.com!eternal-september.org!feeder.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups: comp.programming
Subject: Re: on 2^O(lg n) being a polynomial
Date: Tue, 28 Mar 2017 14:25:17 +0100
Organization: A noiseless patient Spider
Lines: 42
Message-ID: <87vaqtwn2a.fsf@bsb.me.uk>
References: <86lgrudu6c.fsf@toledo.com>
Mime-Version: 1.0
Content-Type: text/plain
Injection-Info: mx02.eternal-september.org; posting-host="37a2b41bb1d4d7dd0d097f55ea00616a"; logging-data="12255"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+0Ctzti8ppBEAnGJNh3Z+6t93dOZP3u90="
Cancel-Lock: sha1:W550BV/J582bx6a2guoDpqK5jec= sha1:f9hJumFuwG5ayYA6FKuWrziXOUo=
X-BSB-Auth: 1.9202caffd4170945da18.20170328142517BST.87vaqtwn2a.fsf@bsb.me.uk
Xref: csiph.com comp.programming:7662

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.