Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [asymptotics]

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

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-...