# Tagged Questions

Questions involving asymptotic analysis, including growth of functions, Big-O notation, Big-Omega and Big-Theta notations.

31 views

### Show $\dfrac{(n!)^{a}n^{bn}}{\left( (2n)!\right)^{c}}\sim Kn^{(a+b-2c)n}n^{\frac{a-c}{2}}\left(e^{2c-a}2^{-2c} \right)^{n}$

I would like to show: $$\dfrac{(n!)^{a}n^{bn}}{\left( (2n)!\right)^{c}}\sim Kn^{(a+b-2c)n}n^{\frac{a-c}{2}}\left(e^{2c-a}2^{-2c} \right)^{n} \mbox{ with } k=2^{\frac{a}{2}-c}\pi^{\frac{a-c}{2}}$$ ...
71 views

### Why is $\lim\limits_{x \to +\infty}\frac{x \sqrt{x+2}}{\sqrt{x+1}} - x = \frac12$?

I need to evaluate this limit: $$\lim_{x \to +\infty}\frac{x \sqrt{x+2}}{\sqrt{x+1}}-x$$ to calculate the asymptote of this function: $$\frac{x \sqrt{x+2}}{\sqrt{x+1}}$$ which, according to the class ...
13 views

### Hypergeometric function how to detect blow up for large arguments

I have to study 11 solutions to ODEs containing multiple hypergeometric functions of type: $${}_2F_2 \left(\begin{array}{c} a_1,a_2 \\ b_1,b_2 \\ \end{array} ;z \right).$$ My main ...
74 views

### Show that $(-1)^{n}\left(\sqrt{n+1}-\sqrt{n} \right)=\tfrac{(-1)^{n}}{2\sqrt{n}}+\mathcal{O}\left(\tfrac{1}{n^{3/2}} \right)$

I would like to show that : $$\fbox{(-1)^{n}\left(\sqrt{n+1}-\sqrt{n} \right)=\dfrac{(-1)^{n}}{2\sqrt{n}}+\mathcal{O}\left(\dfrac{1}{n^{3/2}} \right)}$$ by starting from the left side and get ...
62 views

28 views

Perform DFS over the entire graph. The linear time taken by a size of graph as visiting each node finished is put it on the head of initially empty list is $O(|V|+|E|)$ $O(|V+E|)$ $O(|V|^k)$ $O(\... 0answers 14 views ### Does make sense define a gauge for the integral$\int_2^x\frac{\sum_{n\leq t}\Lambda(n)}{t}dt$, where$\Lambda(n)$is the von Mangoldt funtion? I try encourage to me to study and understand the definition of gauge integral. See for example this reference Schechter, The Gauge integral where is explained the definition with an example. It is ... 0answers 18 views ### What the most optimal value for sqrt(n^3+n(sin(n))^2) = Big O(?)? In class, I was given this question. Here, I will show step by step on how my teacher did it, but I have some questions. So he said to "bound" it. For all n >= 1, he chooses (sin(n))^2 because it is ... 1answer 126 views ### Proving Lower Bound on Catalan Numbers I'm a student of computer science and was reading through my algorithms textbook about matrix chain multiplication. It brought up Catalan numbers and I was hoping to prove the lower bounds on it. This ... 2answers 51 views ### nature of the series$\sum (-1)^{n}n^{-\tan\left(\tfrac{\pi}{4}+\tfrac{1}{n} \right)}$I would like to study the nature of the following serie: $$\sum_{n\geq 0}\ (-1)^{n}n^{-\tan\left(\dfrac{\pi}{4}+\dfrac{1}{n} \right)}$$ we can use simply this question : Show :$(-1)^{n}n^{-\tan\...
Given two functions $f(n)$ and $g(n)$, is it possible that $f(n) = O(g)$ and that $g(n) = O(f)$? If the answer is yes, I have a follow-up: if $f(n)$ and $g(n)$ are Big-O of each other, does that ...
On the wiki page for forward euler (https://en.wikipedia.org/wiki/Euler_method#Local_truncation_error), it describes the local truncation error like so: $\mathrm{LTE} = y(t_0 + h) - y_1 = \frac{1}{2} ... 1answer 27 views ### Can you provide us an asymptotic for this series involving Mertens functions? Let for integers$k\geq 1$, the Möbius function denoted by$\mu(k)$, and$M(n)=\sum_{k\leq n}\mu(k)$the Mertens function, then one can prove easily that $$\sum_{k=1}^n\mu(k)\frac{e^{\mu(k)}+1}{e^{\... 2answers 55 views ### Asymptotics of f_c(n)=\sum_{k=0}^{\lfloor cn\rfloor}{n\choose k} Define$$ f_c(n)=\sum_{k=0}^{\lfloor cn\rfloor}{n\choose k} $$for some fixed constant c (say, 0<c<1/2). What are the asymptotics of f_c(n) as n\to\infty? It seems that this should be ... 1answer 89 views ### Counting function for sums of three squares Legendre showed that an integer is the sum of three squares if and only if it is not of the form 4^n(8m + 7) for some nonnegative integers n and m. However, I have been unable to find any ... 0answers 33 views ### Asymptotic expansion of elliptic integral I am trying to find the first 2-3 terms of the asymptotic expansion in terms of 1/ρ of the elliptic integral I_n(\rho)=\int_0^\frac{h_2}{\rho}\frac{t^{2n}/h_2^{2n}}{(E_n(t))^2\... 3answers 131 views ### What is the value of I=\lim_{n \to \infty} \int_0^1 {{1 + nx^2}\over{(1 + x^2)^n}} \log(2 + \cos(x/n))\,dx.? Find the integral I.....it looks like a good problem which I was not able to solve ....please help...$$I=\lim_{n \to \infty} \int_0^1 {{1 + nx^2}\over{(1 + x^2)^n}} \log(2 + \cos(x/n))\,dx.$$3answers 1k views ### Running time (Big O) of counting in binary What is the total running time of counting from 1 to n in binary if the time needed to add 1 to the current number i is proportional to the number of bits in the binary expansion of i that must ... 0answers 23 views ### When is \frac{2 n f(n)}{n !} in the order of some fixed power of n? I would like to know when \frac{2 n f(n)}{n !} is O (n^b) where b is a constant. Here, n is a positive integer. My attempt:$$ \frac{2 n f(n)}{n !} = \frac{2 n f(n)}{\sqrt{2 \pi n} (\frac{n}{... 1answer 59 views ### Show :$(-1)^{n}n^{-\tan\left(\tfrac{\pi}{4}+\tfrac{1}{n} \right)}=\tfrac{(-1)^{n}}{n}+\mathcal{O}\left(\tfrac{\ln(n)}{n^{2}} \right)$I would like to show that : $$(-1)^{n}n^{-\tan\left(\dfrac{\pi}{4}+\dfrac{1}{n} \right)}=\dfrac{(-1)^{n}}{n}+\mathcal{O}\left(\dfrac{\ln(n)}{n^{2}} \right)$$ My proof: Note that : \begin{... 0answers 19 views ### Show that$\tfrac{(-1)^{n}}{\cos(n)+n^{\tfrac{3}{4}}}=\tfrac{(-1)^{n}}{n^{\tfrac{3}{4}}}+\mathcal{O}\left( \tfrac{1}{n^{\tfrac{3}{2}}}\right) \$
I would like to show that : $$\dfrac{(-1)^{n}}{\cos(n)+n^{\tfrac{3}{4}}}=\dfrac{(-1)^{n}}{n^{\tfrac{3}{4}}}+\mathcal{O}\left( \dfrac{1}{n^{\tfrac{3}{2}}}\right)$$ by starting from the left side ...