Questions tagged [asymptotics]
Questions involving asymptotic analysis, including growth of functions, Big-O notation, Big-Omega and Big-Theta notations.
5,781 questions
0
votes
3answers
28 views
Why does this rational function have a false slant/oblique asymptote?
Let's examine the following rational function: $f(x) = \frac{3x^3+2}{x^2-x-7}$.
Considering that the degree of the polynomial in the numerator is 1 greater than that of the denominator, it can be ...
3
votes
0answers
42 views
How to handle little $o$ in the central limit theorem
I am having some trouble understanding a couple of lines in the proof of the central limit theorem using characteristic functions:
https://en.wikipedia.org/wiki/Central_limit_theorem#...
1
vote
2answers
21 views
Prove or disprove $f \in O(g)$, with $f=5^{\log(n)^2}$ and $g = n^{\log(n)}$
I have a feeling $f$ grows faster than $g$, and therefore it is not the case that $f \in O(g)$, but no matter how much I try, I do not see how to prove it.
Any help?
0
votes
0answers
17 views
Anirban DasGupta Asymptotic Theory Book
Iam having a huge difficult to understand Asymptotic Theory in Statistic/Probability.
Ive Found Anirban DasGupta Asymptotic Theory Book, but there is not the solution for the exercise.
First I ...
0
votes
0answers
40 views
How to find asymptotes of $xy^2-x^2 y+2x-y=6$
So ive been set this question by my lecturer and i have always had a provlem with asymptotes.
So far i managed to get the equation into y = mx+C form making it
$$
X(M^2X^2+2MCX+C^2)-X^2(MX+C)+2X-MX+...
1
vote
0answers
30 views
If $f(n)=\omega(g(n))$ then exists $h(n)$ so $h(n)=\omega(g(n))$ and $f(n)=\omega(h(n))$?
True or false: If $f(n)=\omega(g(n))$ then exists $h(n)$ so $h(n)=\omega(g(n))$ and $f(n)=\omega(h(n))$?
I think this is true but can't seem to prove it. I tried playing around with the definition ...
0
votes
0answers
13 views
Worst-case running time of getting “irreducible substrings” of an input string.
Define $t \leqslant s$ to mean that $t$ is a substring of $s$, which always includes the empty string.
Define $R_s = \{ t \leqslant s: |t| \geq 2, \ t \gamma t \leqslant s, \text{ for some } \gamma \...
0
votes
0answers
22 views
Harmonic series (double)
I am wondering about the $\Theta$ class (i.e. asymptotic complexity) of the following:
$$\sum^n_{i=1} \sum_{j=1}^n \frac{1}{ij}$$
Since this is basically the harmonic series, applied twice, it ...
1
vote
3answers
46 views
Is it true that $n/\log(n)$ is approximately $\log(n/\log(n))$ for large enough $n$
Someone wrote this on a homework assignment I'm grading:
$n/\log(n)$ is approximately $\log(n/\log(n))$ for large enough $n$
Is there an easy way to see it as true or false?
0
votes
1answer
19 views
How to prove that $ n^b \neq O(n^a) $, if b > a > 1
How can we prove that $n^b \neq O(n^a) $, if b > a > 1
Based on Big-O definition:
$n^b \neq O(n^a) \iff |n^b| \le c|n^a|$
I know it's funny but I am stuck here and can't figure it out
1
vote
1answer
16 views
Rate of convergence precise meaning/definition
In the context of mathematical statistics, people often say MLE's rate of convergence is $\sqrt{n}$ as $\sqrt{n}(\hat{\theta}_n-\theta_0) \to N(0,V)$ in distribution. But is there any official ...
0
votes
0answers
27 views
Quadratic programming: Approximate Solution
Let $A$ be a $p \times p$, positive definite and symmetric matrix and $t \in \mathbb{R}^p$, such that $t_i>0$ for at least one $i \in \{1,\dots,p\}$. Let $x^*$ be the unique minimizer of
$$min \{x'...
0
votes
0answers
19 views
How to find asymptotics of indefinite integrals
Often, an indefinite integral cannot be expressed exactly. It would be useful if it were possible to at least prove something about asymptotics of the indefinite integral.
I wasn't able to find much ...
1
vote
0answers
50 views
Asymptotics In Probability Theory Help
I have a problem with a random walk I'm trying to work with.
Suppose I have a random walk
$$S_n = \xi_1 + ...+\xi_n, n \geq 1, S_0= 0$$
with i.i.d. increments $\{\xi_n\}$ with common distribution
...
1
vote
1answer
18 views
How to compute asymptotic confidence interval for linear regression?
Just to make it simple, let us assume we have data $(x_1,y_1), (x_2, y_2),...,(x_n,y_n)$ and perform a linear regression:
$y = \alpha + \beta x + \epsilon$
I know how to compute the exact confidence ...
-4
votes
1answer
28 views
Integral of $ \int \left( 1 + \frac {\log (x)}{x} + O \left( \left( \frac {1}{x} \right)^2 \right) \right) dx $?
How would we integrate a function with a Big O notation like this:
$$ \int \left( 1 + \frac {\log (x)}{x} + O \left( \left( \frac {1}{x} \right)^2 \right) \right) dx $$
0
votes
1answer
33 views
Asymptotics of the reciprocal Riemann Zeta Function
Assuming Riemanns hypothesis, I would like to obtain an upper bound on
$$\left|\frac{1}{\zeta(\sigma+it)}\right|$$
for large $t$ and fixed $\sigma$. I believe it should be easy to show that it ...
0
votes
0answers
15 views
Litle-$o_p$ notation question
Suppose that $f_n/f = 1-o_p(1)$. Is this equivalent to saying $f_n/f \overset{p}{\to} 1$? Or is one weaker than the other?
-1
votes
1answer
28 views
Asymptotic Notation: Does f in o(g) imply g not in O(f)?
Does $f \in o(g)$ imply $g \not\in O(f)$?
Thank you very much for your help!
0
votes
0answers
54 views
Prove that $\frac d {dz} \ln(\Gamma(z)) ∼ \ln(z) − \frac 1{2\,z}$
What steps do I take to figure this out?
I've tried using this: $z!\sim \sqrt{2\,\pi\,z} \left(\frac z e\right)^2$
1
vote
1answer
37 views
Weird Number Density, confusion regarding Wolfram Mathworld definition
Wolfram MathWorld says:
An infinite number of weird numbers are known to exist, and the sequence of weird numbers has positive Schnirelmann density.
Wikipedia says:
Infinitely many weird ...
0
votes
1answer
11 views
Asymptotic behaviour of Bessel function of the second kind with a negative order
Is there any result on the asymptotic behaviour of Bessel function of the second kind with a negative order? What I have found is the behaviour when the order $Re(\nu)>0$. For example, it is shown ...
1
vote
1answer
46 views
Detailed proof that $an^2+bn+c=\Theta(n^2)$
I am reading the book "Introduction to Algorithms", 3rd Edition, by Cormen, Leiserson, Rivest and Stein, and on page 46, they write the following:
"[…] consider any quadratic function $f(n)=an^2+bn+...
0
votes
0answers
18 views
Schnirelmann density and Natural Density
I've been curious about the densities of certain sets of integers and I've come across 2 types: natural or asymptotic density and Schnirelmann density.
Natural density is given by $a$ such that:
$$a=\...
1
vote
0answers
31 views
What is going on with these asymptotics for $\mathrm{Re}\left\{ \ _2F_1\left(\tfrac{1}{2}, \tfrac{5}{2} ; 2 ; x \right) \ \right\}$
I am interested in the large $x$ asymptotics for the function
$$
\mathrm{Re}\left\{ \ _2F_1\left(\tfrac{1}{2}, \tfrac{5}{2} ; 2 ; x \right) \ \right\}
$$
When I check the series expansion at $x = \...
2
votes
1answer
32 views
Asymptotics of integrals with respect to asymptotically equivalent distribution functions
Let us assume that $f\colon[0,\infty)\to[0,\infty)$ is a non-decreasing continuous function with
$$ \frac{f(t)}{t}\xrightarrow{t\to\infty}1. \tag{A}\label{A}$$
We then have the following elementary ...
2
votes
0answers
15 views
Calculations on matrix with asymptotic entries [Big oh and Little oh notation].
Suppose a nonnegative sequence $h=h_n$ satisfying $h\rightarrow 0$ and $nh\rightarrow \infty$ as $n \rightarrow \infty$. Consider the asymptotic notation 'Big Oh' and 'small oh'. Define
\begin{...
1
vote
2answers
43 views
Prove or disprove $n^2 \log{n} = O(n^2)$
I'm having troubles grasping Big-Oh notation and complexities. How do I go about either proving or disproving this statement?
0
votes
1answer
23 views
Approximating when variable to infinity
In a book on algorithms I read that $n^2 (1+\log n)$ as $n$ approaches infinity is approximated to $n^2 \log n$.
I am not sure if I understand reasoning in this. Is it because $1+\log n$ grows so ...
0
votes
0answers
34 views
Compare the growth of given functions.
Compare the growth of the following 2 functions:
$$n^{\log \log \log n}$$
$$(\log n)!$$
My solution:
Let $n=2^m$
$$n^{\log \log \log n}=(2^m)^{\log \log \log_2 m}$$
$$=(2^m)^{\log \log m)}$$
$$=(\...
2
votes
1answer
67 views
asymptotics for binomials
What is a published reference for the asymptotic equivalent of $ n \choose k$ with $k$ linear in $n$? I want both the entropy function and the denominator in $\sqrt{n}.$
0
votes
1answer
38 views
Compare the growth rate of given functions.
In this problem we have to compare the growth rate of the following functions.
$$n^{log n}$$
$$(log n)^{n}$$
I have tried to solve this question but got stuck at a point.
My solution:
Let$$n=2^m$$
$...
0
votes
1answer
59 views
What is the growth rate of a function $f(n)=\sum_{i=1}^\infty (1-1/n)^{i(i-1)/2}$?
I want to find the growth rate of the function $$f(n)=\sum_{i=1}^\infty (1-1/n)^{i(i-1)/2}$$
Since $(1+x)^k\approx 1+kx$ for $|x|\ll1$, I modified $f(n)$ to
$$ f(n) \approx \sum_{i=1}^\infty \left[1-\...
0
votes
2answers
15 views
$f,g:\mathbb{N}\to\mathbb{N}$ increasing implies $g\in \Omega(max(f(n),g(n))$ or $f\in \Omega(max(f(n),g(n))$
studying for a test I encountered a problem that should be easy. Unfortunately, I fail to solve it.
let $f,g:\mathbb{N}\to\mathbb{N}$ be increasing functions.
assume $f\notin \Omega(max(f(n),g(n))$,
...
0
votes
1answer
25 views
confusion with a manipulation in a equation
In line(5), I dont understand why the $O(k^2)$ and $O(h^2)$ became linear in the lhs. Is it because
$$ k C + O(k^2) = O(k) $$
where $C = \frac{u_{tt}}{2} $ ??
0
votes
1answer
40 views
Solving the recurrence $T(n)=2T\left(\frac{n}{2}\right)+6n+\log(n)$
$$T(n)=2T\left(\frac{n}{2}\right)+6n+\log(n)$$
Using the master theorem is seems to be both in case $2$ and case $3$.
Is there another way to approach this?
I tried this:
$$T(n)=2\cdot 2\cdot (2T\...
3
votes
1answer
34 views
Showing $7n^2 + n = \Omega(n)$
I have the intution of how this is true but I am facing problem to write it mathematically. Can someone help me with this?
$$7n^{2} + n=\Omega(n)$$
0
votes
1answer
43 views
Solving the recurrence $T(n) \le 2T(n−1)+n$
Solve the recurrence relation $T(n) \le 2T(n−1)+n$ , given that $T(1) = 1$, to obtain an asymptotic upper bound for $T(n)$ in terms of big-O.
I believe I need to do this with the substitution method, ...
2
votes
3answers
68 views
Asymptotic expansion of the sequence $u_n=\sum\limits_{k=1}^{n}e^{-b^{-k}}$
Let $\left(u_n\right)_{n\in\mathbb{N^*}}$ be the sequence defined $\forall n\in\mathbb{N^*}$ by :
$$u_n=\sum\limits_{k=1}^{n}e^{-b^{-k}}$$
With $b\in(1,+\infty)$.
We can instictively say that when $n\...
3
votes
1answer
84 views
Alternating shifted central binomial sum with Cauchy weights
My question is how can one show that
$$\lim_{n \to \infty} \frac{1}{\binom{2n}{n}}\sum_{k=1}^n (-1)^k \binom{2n}{n+k}\frac{x^2}{x^2+\pi^2k^2} = \frac{1}{2}\Big(\frac{x}{\sinh(x)}-1\Big) $$
I find ...
-2
votes
0answers
19 views
Proving equation in Big-O
I am trying to prove the following equation using the mathematical definition of Big-O. Which is:
O(f(n)) = O(k*f(n))
Equation to solve
0
votes
0answers
15 views
Find the number of total operations executed and the complexity of the code?
enter image description here
How do we find the total number of operations? and why did they divide by 2?
The second question is how to find the big O?
1
vote
1answer
14 views
sum of Time complexities
Question: Say we have $f(n) = O(n)$ and $g(n) = O(n)$, Show (or not) that $f(n) + c g(k) = O(n+k)$
Solution:
We have : $f(n) = O(n) \Leftrightarrow \exists a \ \textrm{ and } \ n_0 \ \textrm{ s.t. }...
1
vote
0answers
30 views
Combining little-o notation
Suppose we have $$f_{m}(n) = \frac{1}{n}g_{m}(n) + o(\frac{1}{n})$$ where the little-o notation is uniform in the variable $m$ as $n \rightarrow \infty$. Under what conditions is $f(m,n) = o(\frac{1}{...
1
vote
1answer
40 views
Show $\frac{n+1}{2n^2+5} \in \Theta (\frac{1}{n})$ using definition
Show $\frac{n+1}{2n^2+5} \in \Theta (\frac{1}{n})$ using definition
First showing the upper bound
$\frac{n+1}{2n^2+5} \in O (\frac{1}{n})$
$\frac{n+1}{2n^2+5} \leq \frac{2n}{2n^2} = \frac{1}{n}$
...
3
votes
1answer
26 views
Sharp bounds for the principal branch of the Lambert W function?
I'm looking for references for bounds on the principal $W_0$-branch of the Lambert W-function, specifically in the range $[ -\frac 1e, 0)$. I'm trying to work with the expression $W(-xe^{-x})$ with $x ...
1
vote
2answers
94 views
Meaning of $ e^x = 1 + x + \Theta(x^2)$?
In the CLRS book chapter 3: When $x → 0$, the approximation of $e^x$ by $1+x$ is quite good:
$$e^x = 1 + x + \Theta(x^2)$$
How is it to be interpreted, what is the role of asymptotic notation here? ...
1
vote
1answer
23 views
Reciprocal of $x_{n-1}^2(1-\frac{x_{n-1}^2}{3}+o(x_{n-1}^2))$ where $x_n\searrow0$
Suppose that $\{x_n\}$ is a decreasing sequence having limit $0$. How to find the reciprocal of $x_{n-1}^2(1-\frac{x_{n-1}^2}{3}+o(x_{n-1}^2))$ as $n\to\infty$.
In my textbook it says that
\begin{...
1
vote
2answers
42 views
Asymptotics of Hypergeometric $_2F_1(a;b;c;z)$ for large $|z| \to \infty$?
I found this list of asymptotics of the Gauss Hypergeometric function $_2F_1(a;b;c;z)$ here on Wolfram's site for large $|z| \to \infty$
In particular there is a general formula for $|z| \to \infty$
$...
0
votes
1answer
72 views
Asymptotic behavior of $\sum\limits_{n=0}^{\infty}x^{b^n}$ when $x\to1^-$
This follow my previous post here, where Song has proven that $\forall b>1,\lim\limits_{x\to 1^{-}}\frac{1}{\ln(1-x)}\sum\limits_{n=0}^{\infty}x^{b^n}=-\frac{1}{\ln(b)}$, that is to say :
$$\forall ...
