Stack Exchange Network

Stack Exchange network consists of 174 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
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 ...