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

Groups > comp.programming > #7670

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

Show all headers | View raw

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.

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