on 2^O(lg n) being a polynomial

Path	csiph.com!aioe.org!.POSTED!not-for-mail
From	Daniel Bastos <dbastos@toledo.com>
Newsgroups	comp.programming
Subject	on 2^O(lg n) being a polynomial
Date	Fri, 24 Mar 2017 22:25:15 -0300
Organization	Aioe.org NNTP Server
Lines	22
Message-ID	<86lgrudu6c.fsf@toledo.com> (permalink)
NNTP-Posting-Host	BuEqJTf8bEmpZhBIUMG+Zw.user.gioia.aioe.org
Mime-Version	1.0
Content-Type	text/plain
X-Complaints-To	abuse@aioe.org
User-Agent	Gnus/5.13 (Gnus v5.13) Emacs/24.3 (windows-nt)
Cancel-Lock	sha1:4QvreAuyS8wnHnp9p+APTGlzkRI=
X-Notice	Filtered by postfilter v. 0.8.2
Xref	csiph.com comp.programming:7634

Show key headers only | View raw

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

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

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.

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

Back to comp.programming | Previous | Next — 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