Path: csiph.com!aioe.org!.POSTED!not-for-mail From: Daniel Bastos Newsgroups: comp.programming Subject: on 2^O(lg n) being a polynomial Date: Fri, 24 Mar 2017 22:25:15 -0300 Organization: Aioe.org NNTP Server Lines: 22 Message-ID: <86lgrudu6c.fsf@toledo.com> NNTP-Posting-Host: BuEqJTf8bEmpZhBIUMG+Zw.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:4QvreAuyS8wnHnp9p+APTGlzkRI= X-Notice: Filtered by postfilter v. 0.8.2 Xref: csiph.com comp.programming:7634 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.