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

learn more… | top users | synonyms (1)

1
vote
3answers
62 views

Show $f(x) = (x^4+x^2+1)/(x^3+1) $ is $O(x)$

How would I find the witnesses $C$ and $k$ such that $f(x)$ is $O(x)$? What I tried was $$(x^4+x^2+1)/(x^3+1) ≤ (x^4+x^4+x^4)/(x^3+x^3) = (3/2)x $$ for values $x>1$. $C = 3/2, k = 1$ Is this ...
2
votes
1answer
290 views

Derivative of big O symbol

Let's only work with functions $f(x)$ that have a series expansion at $x=0$. Is it true that: $$ {d O(1)\over d x} = O(1) $$ for all such functions $f(x)$? Here $O$ is the big-O notation and we are ...
4
votes
2answers
183 views

Asymptotic behavior of $\sum_{n>x} \frac{\log n}{n^2}$

There is a well-known question that seeks the asymptotic behaviour of this function, for $x\geq 2$: $$\sum_{n\leq x} \frac{\phi(n)}{n^2}.$$ See, for example, Apostol "Introduction to Analytic Number ...
2
votes
1answer
66 views

asymptotic approximation when $a\to 0^+$ of $I(a):=\int_0^\infty \int_0^{a/x}e^{-x-y}\ dy\ dx.$

I want to find an asymptotic approximation when $a\to 0^+$ for the integral $$I(a):=\int_0^\infty \int_0^{a/x}e^{-x-y}\ dy\ dx.$$ I found the following approximation: $$C_1\, a\, \mathrm{ln}(1/a) ...
1
vote
1answer
76 views

Nesting big-O with big-Omega $O(g(\Omega(h(n))))$: is it $O$ for all $\Omega$ or for one $\Omega$?

I want to express the following statement about a function $f(n)$: there exists $f_\Omega\in\Omega(h(n))$ such that $f\in O(g(f_\Omega(n))$. What's the correct notation for this? Is it $f\in ...
8
votes
1answer
190 views

Speed of convergence of Riemann sums

This question is inspired by a previous question. It was shown that, for all function $f \in \mathcal{C} ([0, 1])$, $$ \lim_{n \to + \infty} \sum_{k=0}^{n} f \left( \frac{k}{n+1} \right) - ...
26
votes
3answers
584 views

Expected length of the shortest polygonal path connecting random points

$N$ points are selected in a uniformly distributed random way in a disk of a unit radius. Let $L(N)$ denote the expected length of the shortest polygonal path that visits each of the points at least ...
4
votes
2answers
117 views

how to find the asymptotic expansion of the following sum:

I need to determine an asymptotic expansion when $q \rightarrow 1$ of the sum $$S(q)=\sum_{n=0}^{\infty} \frac{q^n}{ (q^n + 1)^2 }.$$ Numerical computations suggest that $S(q)\sim\frac{c}{|q-1|}$ ...
2
votes
1answer
103 views

Lommel function

I need to do this integral: $$\int_0^\infty dx\cdot x \sqrt{x^2+1}K_0(ax)$$ where K is the modified Bessel of second kind. I have seen that in Gradhsteyn 7th edition in 6.565.7 says that this ...
5
votes
1answer
184 views

Obtaining the Airy kernel from the Christoffel-Darboux formula with asymptotic Hermite polynomials

Let the Kernel associated to a family of orthogonal polynomial $p_n(x)$ with weight $w(x)$ be defined as $$K_N(x,y):=\frac{\sqrt{w(x)w(y)}}{\int w(x) p_{N-1}(x)p_{N-1}(x)dx} ...
0
votes
2answers
39 views

Show Time $T(n) = Θ(n^3)$

I have to show that : $$T(n) = Θ({n^3})$$ We have this recursive function : $$T(n) = 8T(n/2) + n^2, n>=2$$ also we know that $$T(1) = 1$$ And it says that there is a "replacement method" to ...
1
vote
1answer
119 views

Help understanding solution to growth of partition function

I'm currently a Combinatorics student trying to parse through this solution. I do not understand the proof currently. Any help understanding it is greatly appreciated. Question Let the number of ...
1
vote
0answers
38 views

Simplifying products

Sorry for the very general title, but I don't even know how to name my question. I got a formula which is: $f(n)=\prod_{i = 0}^{\infty} ((n \; \mathrm{rem} \; p^{i + 1}) \; \mathrm{div} \; p^i + 1) ...
2
votes
0answers
44 views

The characterization of asymptotic dimension

Let X be a metric space. The following conditions are equivalent (a)asdimX = n (b)n is the smallest integer such that for every R > 0 there exists n + 1 families Ui i=0,1,2,...,n, and S > 0 such ...
2
votes
0answers
178 views

representing integers as linear combination of integers

Let $a,b,a',b'$ be $r-\epsilon_1$ bit positive integers. Let $c,d$ be $s+\epsilon_2$ bit positive integers. Fix a pair $c,d$ and vary $a,b$ over all $r-\epsilon_1$ bit numbers. Do we have almost ...
1
vote
1answer
51 views

How to prove that sum given by generating function diverges for given value of $x$

I have a generating function: $A(x)=\dfrac{3-8x}{1-4x+6x^2-3x^3}$ (also I have a recurrence from which this function is built). I have to prove that sum $\sum\limits_k a_k\left(\dfrac{4}{3}\right)^k$ ...
1
vote
1answer
89 views

An integral relating to Bernoulli polynomials

Show that $$\int_{0}^{1}B_{2n+1}(x)(\cot({\pi}x)-2\sin(2{\pi}x))dx{\sim}0$$ where $B_{2n+1}(x)$ is the Bernoulli polynomials.
1
vote
1answer
55 views

Asymptotic equality proof with $a_n^2 \ln a_n ~ n$

Given $a_n^2 \ln a_n \sim n$, prove that $a_n \sim \sqrt{\frac{2n}{\ln n}}$. How do I approach this?
4
votes
1answer
107 views

Bernoulli number type asymptotics

I find an interesting formula but I can not prove it. Show that $$I_n=(-1)^{n+1}\int_0^1 B_{2n+1}(x)\cot(\pi x) \, dx\sim\frac{2(2n+1)!}{(2\pi)^{2n+1}}$$ where $B_n(x)$ is the Bernoulli Polynomials.
3
votes
2answers
143 views

Show $S(t) =\sum_{n=-\infty}^\infty\sin{(n^2t^2)}e^{-tn^2}$ is $O(t^p)$ at zero

An old qualifying exam problem: For $t>0$, define $$S(t) =\sum_{n=-\infty}^\infty\sin{(n^2t^2)}e^{-tn^2}.$$ Show that $S(t) = C t^p + o(t^p)$ as $t\to 0$ . Find $C$ and $p$. There are a couple of ...
3
votes
1answer
86 views

Asymptotic behaviour of e * !n - n! , n tends to infinity

What is the asymptotic behaviour of the function $e !n-n!$ , where $!n = n! \sum_{k=0}^n \frac{(-1)^k}{k!}$ is the subfactorial of $n$. I tried Wolfram Alpha but the series for n=$\infty$ is ...
1
vote
0answers
47 views

Steepest descent?

Here I would like to see the behavior of a function as an integral when its argument (which is a parameter in the integral) goes to zero. If I try to evaluate an integral ...
0
votes
1answer
37 views

Asymptotic distribution of $\left(1-\frac{1}{n}\right)^{n\bar{X}_n}$

Suppose $X_1,X_2, \cdots$ are i.i.d. observations from a $Poisson(\lambda)$ distribution. Define $\bar{X}_n=\sum_{i=1}^nX_i/n$. What will be the asymptotic distribution of ...
2
votes
2answers
216 views

Asymptotic expansion of an integral

I came up with a simpler example which illustrates the technical difficulty I have encountered in my work. Consider an integral depending on parameter $\epsilon$: \begin{equation} ...
2
votes
2answers
77 views

Proof that asymptotic density $>1/n$ implies every sufficiently large integer is the sum of $n$ terms

Gerry Myerson commented on a previous question, which at the time asked for proof that every integer is a sum of two deficient numbers, "The deficient numbers have natural density strictly greater ...
0
votes
1answer
42 views

Power Series Expansion Asymptotics

From my text: Given $\cos^n(x),$ set $x=\frac{\omega}{\sqrt{n}}$, then a local expansion yields: $\displaystyle\cos^n(x)=e^{n\log\cos(x)}=e^{(-\frac{\omega^2}{2}+O(n^{-1} \omega^4))}$ ...
1
vote
1answer
388 views

Laplace transformation of a polynomial function involving square root (or approximation of the integral)

Could somebody suggest how to solve this Laplace transform: $$ \int_0^\infty{e^{-at}\over\sqrt{A+Bt+Ct^2}}{\rm d\,}t $$ ? The real coefficients $A,B,C$ are chosen such that the roots of $A+Bt+Ct^2$ ...
0
votes
1answer
27 views

Asymototics of a real sequence in a Riemann sum

Let $t<0$ and $f(k)\in O(|k|^{t})$ a real function, $k\in\mathbb{Z}$. We consider $$a_n\cdot \sum_{k=1}^n \frac{1}{n} \frac{f(k)}{n^t}$$ where $a_n\subset \mathbb{R}$ and ...
2
votes
2answers
29 views

Growth of series with decreasing numerators and increasing deonimators

It is known that $$H(n)=1+\dfrac12+\ldots+\dfrac1n$$ grows with the same rate as $\log n$. Therefore, $$nH(n)=n\left(1+\dfrac12+\ldots+\dfrac1n\right)=\frac n1+\frac n2+\ldots+\frac nn$$ grows with ...
4
votes
1answer
91 views

Asymptotics of coefficients in the expansion of $\log\cos x$

Let $c_n$ be the coefficient of $x^{2n}$ in the Maclauren expansion of $\log\cos x$. What can be said about the asymptotics of $c_n$ as $n\to\infty$? I expect that this question is routine, but I ...
1
vote
0answers
71 views

Boundary layer method

I am trying to solve the following differential equation using boundary layer method. $\psi ''(z) + \frac{1}{z} \psi'(z)(3 - \frac{4}{1+(\frac{z}{zc})^8})+ \frac{m^2}{1+(\frac{z}{zc})^8}\psi(z)=0$ ...
0
votes
1answer
42 views

Big Oh and Big Omega clarification

Can I get an explanation of: Can g(n) be Big O of $n^{2}$ and also the Big O of $n^{3}$? (at the same time) Can g(n) be Big Omega of $\Omega (n)$ and also be the Big O of $n$?
1
vote
3answers
70 views

Asymptotic relationship demonstration

I have to demonstrate that if $$ \begin{split} f_1(n) &= \Theta(g_1(n)) \\ f_2(n) &= \Theta(g_2(n)) \\ \end{split} $$ then $$ f_1(n) + f_2(n) = \Theta(\max\{g_1(n),g_2(n)\}) $$ Actually I ...
3
votes
0answers
88 views

Asymptotic solution for $T(n) = 6T(n/4) + n \lg n$

I am given that $T(n) = 6T(n/4) + n \lg n$ and want to find $\Theta(T(n))$. Below is what I have typed up for my solution so far; I asked my professor because I was unsure as to how I could assure ...
-1
votes
2answers
84 views

Prove that $f(n)=n^2+2^n$ is $\cal{O}(g(n))$, where $g(n)=3^n$

Prove that $f(n)$ is $\cal{O}(g(n))$, where $$f(n)=n^2+2^n$$ $$g(n)=3^n$$ I tried finding the limit using l'Hôpital's rule and breaking it into parts but it got too complicated.
0
votes
1answer
95 views

Derive asymptotic behavior of inverse of the normal cdf with respect to 2^n

I have a normal distribution $\mu = 0$ and $\sigma = 0.58n$ where $n > 0 $ and I am trying to derive the asymptotic behavior of the following equation: ...
3
votes
1answer
217 views

Asymptotic approximation of sum $\sum_{k=0}^{n}\frac{{n\choose k}}{2^{2^k}}$

I need to find the asymptotic approximation of this sum $$\sum_{k=0}^{n}\frac{{n\choose k}}{2^{2^k}}$$ Can you please share a link to theory or hint how it can be solved? Here is my attempt $n ...
0
votes
1answer
396 views

Is this true or false: $\sum_{i=1}^{n} \log(i)$ is the $ \Omega (n\log n)$?

I'm determining if $\sum_{i=1}^{n} \log(i)$ is the $ \Omega (n\log n)$. The summation of the above,$$\sum_{i=1}^{n} \log(i)= \log n!\approx n\log n$$ And checking with big omega $$n\log n \geq c ...
1
vote
2answers
40 views

Determine run-time of an algorithm

Probably a stupid question but I don't get it right now. I have an algorithm with an input n. It needs n + (n-1) + (n-2) + ... + 1 steps to finish. Is it possible to give a runtime estimation in Big-O ...
2
votes
1answer
159 views

How do you simplify this big O sum?

I saw someone interpret $\sum_{i=1}^{n}\mathcal{O}\left(i^{k-2}\right)$ as $\mathcal{O}\left(n^{k-1}\right)$. Is this right? If so, can you explain?
2
votes
2answers
57 views

What can we conclude from “f is not little-o of g”?

Given two functions $f$ and $g$, what does "$f$ is not $o(g)$" mean ? What can we conclude from this statement ? I know "$f$ is $o(g)$" means the limit at infinity of $\frac fg$ is zero. So does ...
1
vote
1answer
86 views

Find asymptotics in a given form $n=(e+o(1))^{f(s)}$

Let $p\to\infty$, $s={\binom {p^4} p}$ and $n={\binom {p^4}{p^2}}$. Find a function $f(s)$ in the following form $$\large n=(e+o(1))^{f(s)}$$ I've tried to use the followinf asymptotics for ...
1
vote
1answer
28 views

Approximating the modulus of a Complex Function near a point.

Let $\Omega$ be a domain in $\mathbb{C}$, and let $z_0 \in \Omega$. Let $f$ be analytic on $\Omega$. Let $z=z_0+re^{i\theta}$ for $r$ small. Assume that $f(z_0) \neq 0$ and $f'(z_0) \neq 0$. I want ...
3
votes
1answer
135 views

Find the constant $c$ in the equation $\max_{a\le n/2}\frac{C_n^a}{\sum_{k=0}^{\lfloor{a/3}\rfloor}C_n^k}=(c+o(1))^n.$

Find the constant $c$ in the equation $$\max_{a\le n/2}\frac{C_n^a}{\sum_{k=0}^{\lfloor{a/3}\rfloor}C_n^k}=(c+o(1))^n.$$ I've tried to use this asymptotics $$C_n^k \sim \frac{n^m}{m!} \sim e^{m\ln n ...
0
votes
1answer
33 views

Big-O evaluation:

I have the expression: $$f_{k}(n,m) = (n - k)(m - k) + f_{k+1}(n,m)$$ which runs until k = n or m. What is the big theta of this function in terms of n,m? A naive approach is to assume that m does ...
1
vote
3answers
370 views

What is the order of the sum of log x?

Let $$f(n)=\sum_{x=1}^n\log(x)$$ What is $O(f(n))$? I know how to deal with sums of powers of $x$. But how to solve for a sum of logs?
0
votes
1answer
47 views

Proving that if $f$ is equal to $g$ asymtotically then their distance tends to zero

How could I prove via limit definition that from $$ \lim_{n \to \infty} \frac{f(n)}{g(n)} = 1 $$ derives $$ \left| f(n) - g(n) \right| \to 0 $$ ? Previous attempt took me to $$ \left| f(n) - g(n) ...
5
votes
6answers
287 views

Asymptotic solution to the integral $\int_{-\pi/2}^{\pi/2} (\alpha + \sin x)^n \cos^2 x\,\mathrm{d}x$

Recently, I have posted a question on how to find a reduction formula for the trigonometric integral $$\int (\alpha + \sin x)^n \cos^2 x\,\mathrm{d}x.$$ This problem seems to be tough, however. When ...
1
vote
1answer
34 views

little-o and 3 functions

If we have 3 function $f$, $g$ and $h$ such that : $f$ is not $o(g)$ $f$ is $o(h)$ Can we conclude that $g$ is $o(h)$ ? i.e is the following true ? $lim_{x \rightarrow \infty} \frac{f(x)}{g(x)} ...
1
vote
1answer
45 views

getting T(n) when I get bigTheta complexity from recurrence relation

I wonder how could I solve the recurrence relation when I calculate complexities. Let me explain it via an example: $T(n)=2T(n/2) +n$. Solve this recurrence relation. I know from the Master theorem ...