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: Sat, 25 Mar 2017 02:39:17 +0000 (UTC)
Organization: Aioe.org NNTP Server
Lines: 23
Message-ID: <20170324193137.247@kylheku.com>
References: <86lgrudu6c.fsf@toledo.com>
NNTP-Posting-Host: hlQwqVQo951TVKyinY4JRg.user.gioia.aioe.org
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:7635

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.