Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [asymptotics]

For questions involving asymptotic analysis, including function growth, Big-$O$, Big-$\Omega$ and Big-$\Theta$ notations.

Questions involving asymptotic analysis, including function growth, Big-$O$, Big-$\Omega$ and Big-$\Theta$ notations.

  • $f(x) = O(g(x))$ as $x \to \infty$ is used to mean that for sufficiently large values of $x$, we have $|f(x)| \leq A g(x)$ for some constant $A$.

  • $f(x)=\Omega(g(x))$ is equivalent to saying that $g(x)=O(f(x))$.

  • $f(x)=\Theta(g(x))$ is used to mean that $f(x)=O(g(x))$ and that $f(x)=\Omega(g(x))$.

9469 questions
5
votes
2 answers

Asymptotic expansion of $\int_0^{\pi/2} dx \sqrt{1-(1-\epsilon^2)\sin^2x}$ as $\epsilon\to 0$

I wish to find the asymptotic expansion of (at least the first few terms) \begin{equation} \int_0^{\pi/2} dx \sqrt{1-(1-\epsilon^2)\sin^2x} \end{equation} as $\epsilon\to 0$. This integral is closed related to the complete elliptic integral of the…
MrBetadine
  • 53
5
votes
2 answers

Asymptotic behaviour of $E_1(-x) = \Gamma(0,-x)$.

Updated question: I think my original question may have been a bit weird, mainly because taking the absolute value of the exponential integral makes little sense, but I have finally achieved something myself by using the defining property $$…
Matthew Neil
  • 43
5
votes
2 answers

Prove that the curve of the function $ f $ has an asymptote near infinity which is parallel to the line $ y=x $

Let $ f $ be a continuous function from $ \Bbb R $ to $ \Bbb R $ satisfying the condition $$(\forall x,y\in\Bbb R) \;|f(x)-f(y)|\ge |x-y|$$ If we assume that $ f $ is increasing and that $$(\forall x\in \Bbb R)\;f(x)
hamam_Abdallah
  • 62,951
5
votes
1 answer

For which x does $\sum\limits_{i=0}^{n}x^i=O(n)$ hold?

I'm stuck with this exercise: I have to find for which $x$ the estimate $\displaystyle\sum\limits_{i=0}^{n}x^i=O(n)$ holds. It seems intuitive to me that this must be the case for all $x \in (0,1)$ but proving this seems to be beyond my abilities. I…
Brutos
  • 155
5
votes
1 answer

Asymptotics of a function involving factorials

I want to understand the asymptotics of a function which depends on a parameter $N$ which is a large integer. The function is of the form (variable $x$ is of order 1) $$ F_N(x)=\sum_{n=0}^\infty f_{N,n}x^n.$$ I suspect that the coefficient $f_{N,N}$…
thedude
  • 1,777
5
votes
1 answer

Asymptotic expansion of $\sum_{k=0}^n \frac{\ln(k+x)}{(k+x)}$ at $n \to \infty$

Can someone help me get an asymptotic expansion for $$\sum_{k=0}^n \frac{\ln(k+x)}{(k+x)}$$ at $n=\infty$, where $x$ is fixed, I need it with accuracy up to like $O(n^{-3})$, I expect there to be some generalized stieltjes constants in the…
Ethan Splaver
  • 10,613
5
votes
0 answers

How to prove that big O definition is equivalent to its limit definition?

Definition of big $O$: $f(n) = O(g(n))$ if there are positive constants $c$ and $k$, such that $0 ≤ f(n) ≤ cg(n)$ for all $n ≥ k$. The limit definition of big $O$: $f(n) = O(g(n))$ if $ \displaystyle\lim_{x\to \infty} \frac{f(n)}{g(n)} = c $…
user422489
  • 277
5
votes
2 answers

Asymptotic growth of $\prod_{k=1}^n \frac{k^\alpha}{\lambda + k^\alpha}$?

Can you please explain why for $\lambda > 0$ and $0 < \alpha < 1$ $$\prod_{k=1}^n \frac{k^\alpha}{\lambda + k^\alpha} \sim \exp\left(-\frac{\lambda}{1-\alpha}n^{1-\alpha}+o(n^{1-\alpha})\right)$$ holds? I'm stuck at the moment. EDIT: added $o()$…
Haderlump
  • 375
5
votes
1 answer

Estimate sum with a very small error

Estimate sum: $$\sum_{i=1}^{n}\frac{i}{n^2+i}$$ with an absolute error $O\left(\frac{1}{n^2}\right)$ So far, estimation with integrals was sufficient for me, but here the error has to be very small and I don't know how to approach.
ray
  • 1,507
5
votes
2 answers

How is it posible that $f + g \in O(f)$?

I am confused how to do this question. Intuitively it doesn't even make sense how a function $f$ plus another function is in $O(f)$. How can I approach this question: $$ n\log(n^7)+n^{\frac{7}{2}} \in O(n^{\frac{7}{2}}). $$ We know the fact that…
Amir Mousavi
  • 171
5
votes
2 answers

Observation: $\big(\frac{\sin x }{x}\big) ^n \sim e^{-a_n x^2}$

I have observed that this $$\big(\frac{\sin x }{x}\big) ^n \sim e^{-a_n x^2}$$ (It can be fitted better than this, but I did not want them to completely overlap) I want to learn how I would find $a_n$, or if this relationship is technically…
Gappy Hilmore
  • 3,937
5
votes
5 answers

Which function grows at a faster rate? $n!$ or $2^{n^2}$

I have two functions: $n!$ $2^{n^{2}}$ What is the difference between the growth of these two? My thought is that $2^{n^2}$ grows much faster than $n!$.
Dylan Jean
  • 51
5
votes
2 answers

Big-$O$ for $\frac{1}{1-x}$

I would like to show as $x\rightarrow 0$ $$\frac{1}{1-x}= 1+x^2+x^3+\dots+x^n +O(x^{n+1})$$ My inclination is to multiply by $1-x$ to get: $1=(1-x)(1+x^2+\dots+x^n) +(1-x)O(x^{n+1})$ and then, for some constant $C$: $1=x^{n+1}-1 +(1-x)C|x^n|$ But I…
user12802
5
votes
7 answers

Is it true that $2^n$ is $O(n!)$?

I had a similar problem to this saying: Is it true that $n!$ is $O(2^n)$? I got that to be false because if we look at the dominant power of $n!$ it results in $n^n$. So because the base numbers are not the same it is false. Is it true that $2^n$ is…
Hyune
  • 101
4
votes
1 answer

Finding the asymptotics of a summation $\sum_{k=1}^{n}\frac{n-k+1}{k}$

Let $n\in\mathbb{Z}^{+}$ and $\displaystyle S_n = \sum_{k=1}^{n}\frac{n-k+1}{k}$. Finding $\Theta(S_n)$ PS: I found $\mathcal{O}(S_n) = n^2$. Thus, having $(n-k+1)/k = (n+1)/k -1 \leq n$. $\rightarrow S_n = \sum_{k = 1} ^ {n}n = n^2$. But I cant…
qwerty89
  • 726
1 2 3
…
74 75