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

Groups > comp.programming > #7634 > unrolled thread

on 2^O(lg n) being a polynomial

Back to article view | Back to comp.programming

Contents

  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

#7634 — on 2^O(lg n) being a polynomial

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.

[toc] | [next] | [standalone]

#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.

[toc] | [prev] | [next] | [standalone]

#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.

[toc] | [prev] | [next] | [standalone]

#7664

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).

[toc] | [prev] | [next] | [standalone]

#7670

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> 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

What was supposed to be written here?  ``ans do''?  If this is latin, I
need help.  I assumed it was a typo, but can't fix it myself.

> 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 makes a lot of sense now.  I understand the point of the statement
now.  They didn't mean it'd be a polynomial, but that it would
essentially be like one for the context where such topic arises ---
complexity theory.  If f(n) is bounded above by a polynomial, then we
can consider the algorithm being of the order of polynomial time.

I see.  That clarifies everything.  Thanks for your lecture!

>> 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.

Agreed.

[toc] | [prev] | [next] | [standalone]

#7674

Daniel Bastos <dbastos@toledo.com> writes:

> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>> 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
>
> What was supposed to be written here?  ``ans do''?  If this is latin, I
> need help.  I assumed it was a typo, but can't fix it myself.

"and so".  The d and s got swapped.  I think you got the other points
which were the important ones.

<snip>
-- 
Ben.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web