Questions tagged [asymptotics]
Questions involving asymptotic analysis, including growth of functions, Big-O notation, Big-Omega and Big-Theta notations.
5,943 questions
0
votes
0answers
4 views
Approximate distribution of sum of squared standardized Poisson variables
Suppose that $X_1, ..., X_n$ are independent and identically distributed Poisson($\lambda$) random variables.
What is a good approximating distribution for $\sum_{i = 1}^{200} \frac{(X_i - \lambda)^2}...
2
votes
2answers
26 views
Does $2^{O(n)} $ mean $O(2^n)$? If not, what does $2^{O(n)} $ mean?
In this "tutorial", in the end, they say exponential asymptotic notation is $2^{O(n)} $.
Is $2^{O(n)} $ the same thing as $O(2^n)$? Is there any reason to notate it that way?
According to one of the ...
2
votes
1answer
47 views
Proving that $\log(n!)$ is $O(\log n^n)$
I am trying to prove that $\log(n!)$ is $O(\log n^n)$ and I have an intuition for it, but I can't seem to find the constant $c$ that would make $\log(n!) < c \cdot \log(n^n)$ for all $n > n_0$.
...
0
votes
0answers
19 views
Let $\lim_{t\to t_0}\phi(t) = a$. Prove that $f(x) = \mathcal{o}(g(x)) \implies f(\phi(t)) = \mathcal{o}(g(\phi(t)))$
Let:
$$
\lim_{t\to t_0}\phi(t) = a
$$
where $\phi(t)\ne a$ and $t\ne t_0$ in the neighbourhood of $t_0$. Prove that:
$$
\begin{align*}
f(x) \stackrel{x\to x_0}{=} \mathcal{o}(g(x)) &\implies ...
0
votes
2answers
26 views
Asymptotic analysis of harmonic series using Calculus
The problem is to proof that Harmonic series $\sum_{i=1}^n \frac{1}{i} = O(ln \space n)$
So, I know that $ln \space n = \int_{1}^n \frac{1}{x} dx$ so, I need to prove that
$H(n) = 1+\frac{1}{2}+...+...
1
vote
0answers
37 views
$\Delta_g f = 0$ on the Riemannian Manifold $(\mathbb{R}^3 \setminus B , g)$ with conditions on boundary and at infinity
Consider the manifold $M = \mathbb{R}^3 \setminus B$ where $B$ is the ball with radius $1$ with riemannian metric $g$ (not necessarily the euclidean metric).
I am looking for solutions to $\Delta_g ...
4
votes
2answers
62 views
Estimating $\sum\limits_{d\mid n}{d+a\choose b}$
Is there any way of estimating a sum like
$$\sum_{d\mid n}{d+a\choose b},$$
for positive integers $a$ and $b$? For example, in the OEIS we find that
$$\begin{align*}
\sum_{d\mid n}{d+1\choose 2}
&...
1
vote
0answers
25 views
Sums of the form $\sum\limits_{a_1=1}^n\sum\limits_{a_2=1}^{a_1}\cdots \sum\limits_{a_r=1}^{a_{r-1}}{[\gcd(a_1,a_2,\dots ,a_r)=1]}$
Background:
Consider sums of the form
$$\sum_{a_1=1}^n\sum_{a_2=1}^{a_1}\cdots \sum_{a_r=1}^{a_{r-1}}{[\gcd(a_1,a_2,\dots ,a_r)=1]},$$
with $[\gcd(a_1,a_2,\dots ,a_r)=1]$ being equal to $1$ if the ...
0
votes
1answer
24 views
Using O-notation for asymptotic estimation of the number of additions in recursive function
Consider the following python program:
def mystery(n):
if n==0:
return n * n
return 2 * mystery(n//3) + 4 * n
Let call the number of additions ...
1
vote
0answers
70 views
Approximating an infinite sum: $\sum_t t^d \exp(-(t-1)^2/2)$
I am seeking to upper bound the limit of the following infinite summation, when a free parameter $\beta$ can be chosen, perhaps dependent on $d$, to help reduce the sum:
\begin{equation}
f(\beta,d) = \...
0
votes
0answers
49 views
What is the asymptotic behavior of a solution of this ODE?
Consider this ODE:
$$f_{i}’(r) = f_{i}^2 (r) + O\left(\frac{1}{r^4} \right)$$
As $r \to \infty$. $i=1,2$ and the initial conditions are $f_{i} (1) = C_{i} < 0$
This is equivalent to the ODE:
$$...
0
votes
0answers
36 views
Proof verification. Show that $\mathcal{O}(\mathcal{O}(f)) = \mathcal{O}(f)$
Prove that:
$$
\mathcal{O}(\mathcal{O}(f)) = \mathcal{O}(f)
$$
I've started with letting some $u \in \mathcal{O}(\mathcal{O}(f))$, then:
$$
|u| \le k_1|v|
$$
Where:
$$
|v| \le k_2|f|
$$
Which ...
-1
votes
1answer
28 views
order of $ln(1+\epsilon)$ as $\epsilon \rightarrow 0$
I am struggling with understanding how to find the order of this expression. The answer in the solutions is $\lim_{\epsilon \to 0}= \frac{ln(1+\epsilon)}{\epsilon}$. I don't understand the concept of ...
0
votes
1answer
24 views
maximum of the function $f(x) = \sum_{n\geq 1 } \sin n x /n^\alpha $
Here $\alpha >1 $. The function is defined as
$$f(x) = \sum_{n\geq 1 } \sin n x /n^\alpha .$$
The domain is $(0, \pi)$.
We know that if $\alpha = 1$, $f(x) = (\pi -x )/2$.
If $\alpha >1$, ...
0
votes
0answers
29 views
Does there exist an integer sequence that satisfies the following properties?
Does there exist an integer sequence $\{a_n\}_{n = 1}^\infty$ that satisfies the following properties:
$\forall t > 1, n^t = o(a_n)$
$\forall p > 1, q > 0, a_n = o(p^{n^q})$
?
The only ...
0
votes
1answer
37 views
Asymptotic distribution of sample mean of the sum of two poisson distribution
I'm trying to calculate the asymptotic distribution of the sample mean of the sum of two Poisson distributions.
Sample 1 is of size N1, and is from a Poisson distribution with expectation $\mu_1$.
...
1
vote
1answer
55 views
Asymptotic Solution of Recurrence Relations
I have a recurrence relation,
\begin{align}
0 \leq A_{n+1} \leq A_n - c_1 {A_n}^{m} + \frac{c_2}n, ~~~\forall n\geq 1\label{rec}\tag{1}
\end{align}
where $c_1$ and $c_2$ are positive constants, and $...
0
votes
1answer
28 views
Taylor series of complex function confusion with big O notation
Suppose $u(x,t)$ is a function of two real numbers that outputs a complex number.
Usually I would have $u(x,t+k) = u(x,t) + k\frac{\partial u}{\partial t}(x,t) + \frac{1}{2}k^2 \frac{\partial ^2 u}{\...
0
votes
0answers
20 views
Gronwall's Lemma and Non-Stationary Phase Lemma
Suppose we have a function $f \in C^1$ satisfying
$$f(t) = \frac{1}{\epsilon}\int_0^t \sin(s/\epsilon) f(t + \epsilon \sin(s/\epsilon))ds + \phi(t), \quad \epsilon \in (0,1]$$
Is it possible to use ...
0
votes
1answer
59 views
Asymptotic growth of $\frac{k}{1}+\frac{k^2}{1\cdot 2}+\frac{k^3}{1\cdot 2\cdot 4}+\dots$
Let $k$ be a positive integer, and let $$n=\frac{k}{1}+\frac{k^2}{1\cdot 2}+\frac{k^3}{1\cdot 2\cdot 4}+\frac{k^4}{1\cdot 2\cdot 4\cdot 8}+\dots,$$
where the sum goes on until the next term in the sum ...
2
votes
2answers
74 views
Asymptotics of $\sum_{n\geq 1 } \frac{\sin n^2 t }{ n^2 } $
This is the Riemann function.
I would like to determine its asymptotics as $t \rightarrow 0^+ $.
First let $t=x^2 $, so that we treat the series
$$ \sum_{n\geq 1 } \frac{\sin n^2 x^2}{ n^2}. ...
2
votes
1answer
56 views
Is there a formal definition for $f(x)$ ~ g(x)?
I was looking to see if curved asymptotes were possible and came across an answer that referred to an end behavior of a function as being $f(x)$ ~ $x^2$. I'm assuming this either means the end ...
1
vote
1answer
31 views
Asymptotic behavior of Fresnel-like integral of an exponential [on hold]
Given the integral
$$
I(t) = \int_0^t \mathrm{d}x \exp(-[\alpha \cos x + \beta \sin x]),\quad \alpha,\beta\in \mathbb{R},
$$
how can one obtain the asymptotic behavior for $t \to \infty$?
0
votes
1answer
14 views
Asymptotic Notation - Linear Search
Among, Big-O, Big-Omega and Big-Theta, Indicate the efficiency class of a linear search.
The best case (Big-O) for a linear search would be, 1 (or constant) because the item being looked for, could ...
8
votes
1answer
113 views
Does $\sum_{k=1}^n|\cot \sqrt2\pi k|$ tends to $An\ln n$ as $n\to\infty$?
Question: How can we prove that $$L(n)=\sum_{k=1}^n\left|\cot \sqrt2\pi k\right|=\Theta(n\log n)$$ as $n\to\infty$?
Furthermore, if $\sqrt2$ is replaced with a quadratic irrational number, does it ...
0
votes
1answer
31 views
Asymptotic differential equation for large $t$. Can I just drop fast decaying terms?
I am looking at the differential equation
$x'(t)=x(t) (1+s(t))$.
and I want to make a statement about the behaviour of its solution $x(t)$ for large $t$, knowing that for large $t$
$s(t)=\frac{1}{2}...
1
vote
0answers
27 views
Asymptotic behavior of $f(x) = \sum_{n\geq 1 } a_n \cos n x $
Here the coefficients $a_n$ are positive and decreasing in a neighborhood of $+\infty$. Moreover, there is the limit
$$\lim_{n\rightarrow\infty } \frac{a_n }{n^{-3/2}}= \alpha > 0 .$$
What is ...
0
votes
0answers
13 views
Asymptotic number of peaks in a large product of sums of oscillatory functions
I am interested in the following asymptotic question. Suppose I have the function
$$g_N (\alpha_0) = \frac{ \prod_{i=0}^{N-1} \left[\;c_+ (N-i) + c_- (N-i)\cos(2\alpha_0)\;\right]}{\int_0^{2\pi} d\...
2
votes
0answers
31 views
Asymptotics of the Weierstrass function
It is known that the Weierstrass function
$$f (x) =\sum_{n\geq 1 } a^n \cos (b^n x ) , $$
with $0 < a < 1$, $ab>1$, is nowhere differentiable. But this should not prevent us from studying ...
1
vote
0answers
11 views
Property of the remainder term in the Euler-Maclaurin formula for $\sum_{i=1}^n\log i$.
From https://en.wikipedia.org/wiki/Stirling's_approximation, I'm having trouble understanding $$R_{m,n}=\lim_{n\to\infty} R_{m,n}+O(n^{-m}).$$ I worked out $$R_{m,n}=\int_1^{n}\frac{P_m(x)}{mx^m}~ dx$$...
0
votes
1answer
52 views
Contributions from all the saddle points or not?
Consider the following integral:
$$
I(t)=\int_{\mathbb{R}}e^{itp(z)}dz
$$
where $p(z)$ is a real-valued polynomial. And suppose it has both real and non-real critical points, how to find the ...
0
votes
0answers
31 views
Asymptotic analysis of a complex expression.
I am trying to find how $A$ behaves as $n \rightarrow \infty$ and when the parameters $\mu,\eta,v$ are very small that is near zero. The others like $k_{3}<-1$ and $l_{6}>0 , t_{1},u_{1}$ are ...
0
votes
0answers
20 views
Order of growth of partial sums of powers of a bounded sequence
Suppose that $f[x]$ is an infinite sequence taking values in $[0, 1]$ (i.e. it is bounded and non-negative). We want to look at the sequence of partial sums:
$F[x] = \sum_{n=1}^x f[n]$
Let's also ...
1
vote
3answers
27 views
Big-$O$ notation and constant values
Function f(x) $n^3 2^n$ is:
a) $O(\ln n)$
b) $O(n^{3 + n})$
c) $O(2^n)$
d) $O (n^3)$
e) None of the above
Definition:
$f(x)$ is $O(g(x))$ as $x \rightarrow \infty$ if there are positive real ...
0
votes
1answer
25 views
Order the following three function of in increasing order of growth rate
I got this question wrong on my midterm, I need someone to explain how did they get the answer.
$$ A(n) = \frac{2+3n}{5\sqrt{n}(1+4\log{n})} $$
$$ B(n) = \frac{2\sqrt{n}(4+7\log{n})}{\sqrt{n} + 5\log{...
0
votes
1answer
21 views
Representation of an integral with big $O$ terms
Let $\Theta\subset\mathbb{R}$ and consider the integral
$$
\int_\Theta f(t) \left| \frac{1}{\sqrt{n}} g(x_n) t+ r_n(t) \right|dt,
$$
where:
$\bullet$ $n$ is an integer sequence, the sequence of real ...
1
vote
0answers
22 views
Asymptotics of Generating Coefficients along a Ray
Suppose I have a multidimensional array of numbers $a(n_1,\ldots,n_r)$, for $n_1,\ldots,n_r\in\mathbb N\cup\{0\}$. I can form the generating function $$A(x_1,\ldots,x_r)=\sum_{n_1,\ldots,n_r\geq 0}a(...
0
votes
1answer
44 views
Integration (similar to Laplace transform) & limit for large argument
I am faced with the following integral, that looks like essentially finding a Laplace transform, and would like to know how to extract the asymptotic behaviour for large argument. The integral in ...
2
votes
0answers
23 views
Conjecture on the growth of $q_1 = 1, q_{n+1}=q_n + f(q_n) $
This is a generalization
of my answer to
Calculate the limit of the following recurrent series
in the form suggested by
Will Jagy.
$q_1 = 1,
q_{n+1}=q_n + f(q_n)
$
where
$f(x) > 0$
and
$f'(x) <...
1
vote
2answers
36 views
Which of these function grows faster?
I have the functions
$$\frac{n^3}{100000}$$
and
$$\frac{n^3}{\log_2(n)}+100n+5000n^2$$
I can't figure out which one grows faster. Can anyone help me?
0
votes
1answer
17 views
Which of these functions has the fastest asymptotic growth: $n^{1/3}\log_2(n)$ or $\frac{1}{4}(\log_2(n))^4$? [closed]
I can't seem to figure out which of the following functions has the fastest asymptotic growth: $n^{1/3}\log_2(n)$ or $\frac{1}{4}(\log_2(n))^4$? Can anyone show me with a proof?
0
votes
0answers
15 views
What's mean by $\sum_{k=2}^{n-1}c_k\frac{\ell^kd^{1-k\alpha}}{k!}\xrightarrow{d\to\infty}-\infty$ “as fast as $d^{1-2\alpha}$”?
Let $\ell>0$, $\alpha\in(0,1/2)$, $n\in\mathbb N$ with $n>1/\alpha$ and $c_2,\ldots,c_{n-1}\in\mathbb R$ with $c_2<0$. Now let $$S_d:=\sum_{k=2}^{n-1}c_k\frac{\ell^kd^{1-k\alpha}}{k!}\;\;\;\...
0
votes
1answer
38 views
A question on the density of Sophie Germain primes
According to Wikipedia, the density of Sophie Germain primes is expected to be
$$
2C{\frac {n}{(\ln n)^{2}}}\approx 1.32032{\frac {n}{(\ln n)^{2}}},
$$
where $C$ is the twin prime constant. ...
1
vote
0answers
27 views
If $(X_i,ξ_i)$ are mutually independent, then $\text E[|d^{-1/2}\sum_{i=1}^dg'(X_i)ξ_i|^{2q}]$ is bounded by a constant only depending on $q$
Let $d\in\mathbb N$, $X$ be a $\mathbb R^d$-valued random variable on a probability space $(\Omega,\mathcal A,\operatorname P)$ with density $$p(x):=\prod_{i=1}^df(x_i)\;\;\;\text{for }x\in\mathbb R^d$...
0
votes
0answers
17 views
Asymptotic Big-Omega Proof
I wrote a different Big-O proof from what my professor wrote (which involved splitting up the inequality on the right of the implication into three parts and then proving each part individually). Can ...
0
votes
2answers
22 views
Partitioning evens as sum of evens
Take the set $\{a_1,a_2,a_3,a_4,a_5,a_6,a_7,a_8\}$.
We can partition according to rules.
Every member in the partition has even number of elements.
Every member in partition have to be consecutive.
...
0
votes
0answers
14 views
Asymptotic relationship
Consider functions f(n) = n^2 and g(n) = (1 + (-1)^n)n^2. What is the asymptotic relationsip (f is big-theta(g), f is big-omega(g) or f is big-O(g)) between the two functions?
I have graphed the g(n)....
2
votes
1answer
65 views
How to find the real positive root of $x^{k/2} - x - 1$.
Let $k$ be a large even integer. The following polynomial has exactly one real positive root.
$$x^{k/2} - x - 1$$
How can one determine what it is asymptotic to, as a function of $k$?
0
votes
1answer
22 views
Time Complexity of CLRS Optimal Parenthesis Algorithm
I am reading the Introduction to Algorithms CLRS book, and I am unsure about the time complexity of one of the algorithms that is a recursive algorithm that calls itself twice. This chain matrix ...
1
vote
1answer
52 views
Combinatorial identities, check the asymptotic behavior.
Check asymptotic of
C = $\sum_{k = 0}^{\frac{n}{2} - \sqrt{n}} k \binom{n}{k} = f(n) + O(g(n))$
In the beginning I tried to simplify the expression under the sum: $$k\binom{n}{k} = k \frac{n!}{k!(n-...
