0

What is the asymptotic bound for $\sum_{i=0}^{\log(n)} 2^{i} \sum_{k=0}^{\frac{n}{2^{i}}} (k+2)^{2} + \theta(n)$?

Yashar
  • 63

1 Answers1

1

I suggest you use big O notation. If I am not mistaken, the following does the job.

Normal[Series[Sum[2^i*(k + 2)^2, {i, 0, Log[n]}, {k, 0, n/2^i}], {n, Infinity,1}]] //FullSimplify

$$\frac{1}{9} n^3 \left(4-2^{-2 \log (n)}\right)+n^2 \left(5-5\ 2^{-\log (n)-1}\right)+\frac{37 n}{6}+\frac{37}{6} n \log (n)+2^{\log (n)+3}-4 $$

One sees the main term of the asymptotics is $\frac 4 9 n^3$.

Community
  • 1
user64494
  • 5,811
  • According to the documentation O[x]^n represents a term of order $x^n$ not necessarily giving a bound. – yarchik Sep 24 '19 at 07:18
  • @Sorry, don't understand it though I'm PhD in math for ages. Can you kindly elaborate your comment ? – user64494 Sep 24 '19 at 08:30
  • Yes. Consider the Bessel function BesselJ[0,x]. Its leading term in series expansion at infinity reads Sqrt[2/π] Cos[π/4-x]/Sqrt[x]. It represents a good approximation, but does not give a bound such as $|J_0(x)|<1/\sqrt{x}$. – yarchik Sep 24 '19 at 08:57
  • see here https://www.wolframalpha.com/input/?i=plot+besselj%280%2Cx%29+%2C+1%2Fsqrt%28x%29%2C+-1%2Fsqrt%28x%29++from+1+to+300 – yarchik Sep 24 '19 at 09:00
  • @yarchik: Are you serious? The question is about an asymptotic bound and this asymptotic bound as $n$ approaches infinity can be taken $\frac {4+\epsilon} 9 n^3$ with an arbitrary $\epsilon >0$. – user64494 Sep 24 '19 at 09:06
  • I do not question your result. I am stating that in a general setup Series is not a tool to generate the asymptotic bounds. They can be obtained with further analysis based on it. The word bound often comes with a specification "from above" or "from below". This notion is not present in the big-O notation, nor is it a part of Series command. – yarchik Sep 24 '19 at 09:13
  • To finish this thread, up to the common definitions, the upper asymptotic bound under the consideration can be taken $\frac {4+\epsilon} 9n^3$ and the lower one can be taken $\frac {4-\epsilon} 9n^3$ with an arbitrary $\epsilon >0$. – user64494 Sep 24 '19 at 09:21
  • Note that we don't even need Series for this summation. `In[14]:= summation = Sum[2^i*(k + 2)^2, {i, 0, Log[n]}, {k, 0, n/2^i}];

    In[15]:= terms = List @@ Expand[ summation /. a_^(b_. + c_. Log[n]) :> a^b*n^(c Log[a])];

    In[16]:= Last@Sort[terms, AsymptoticLess[##, n -> ∞] &]

    Out[16]= (4 n^3)/9`

     – Greg Hurst Sep 24 '19 at 11:43