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

Path	csiph.com!aioe.org!.POSTED!not-for-mail
From	Kaz Kylheku <336-986-7787@kylheku.com>
Newsgroups	comp.programming
Subject	Re: on 2^O(lg n) being a polynomial
Date	Tue, 28 Mar 2017 17:45:31 +0000 (UTC)
Organization	Aioe.org NNTP Server
Lines	18
Message-ID	<20170328103859.247@kylheku.com> (permalink)
References	<86lgrudu6c.fsf@toledo.com> <87vaqtwn2a.fsf@bsb.me.uk>
NNTP-Posting-Host	hlQwqVQo951TVKyinY4JRg.user.gioia.aioe.org
Mime-Version	1.0
Content-Type	text/plain; charset=UTF-8
Content-Transfer-Encoding	8bit
X-Complaints-To	abuse@aioe.org
User-Agent	slrn/pre1.0.0-18 (Linux)
X-Notice	Filtered by postfilter v. 0.8.2
Xref	csiph.com comp.programming:7664

Show key headers only | View raw

On 2017-03-28, Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
> 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).

That seems to condense to:

   ∃k:2^O(lg n) ⊂  O(n^k)

(Benefits from additional assertion that k is an integer > 1).

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