Path: csiph.com!aioe.org!.POSTED!not-for-mail From: Daniel Bastos Newsgroups: comp.programming Subject: Re: on 2^O(lg n) being a polynomial Date: Tue, 28 Mar 2017 20:28:34 -0300 Organization: Aioe.org NNTP Server Lines: 33 Message-ID: <86vaqtasm5.fsf@toledo.com> References: <86lgrudu6c.fsf@toledo.com> <87vaqtwn2a.fsf@bsb.me.uk> NNTP-Posting-Host: PsmsIGUojJunCAfmNghHww.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:8AqMwMCQoMt7PerbJk0H3HQHtaE= X-Notice: Filtered by postfilter v. 0.8.2 Xref: csiph.com comp.programming:7670 Ben Bacarisse writes: > Daniel Bastos 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.