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
1
vote
2 answers

Asymptotic of $\sum (H_n-H_{k-1})\ln(k)$ where $H_k$ are the harmonic numbers

I want to find the asymptotic of $f(n)=$ \begin{equation} \sum_{k=2}^n (H_n-H_{k-1})\ln(k)=\left(\frac{1}{2}+\cdots+\frac{1}{n}\right)\ln(2)+\left(\frac{1}{3}+\cdots+\frac{1}{n}\right)\ln(3)+\cdots+\frac{1}{n}\ln(n), \end{equation} up to the…
Haoran Chen
  • 659
1
vote
2 answers

Finding the big-$O$ estimate of the solutions to $\cot x = x$

So a problem for my class I am asked to find the big-$O$ estimate (up to 3 terms) of the solutions to $\cot x = x$. We label the solutions to this equation in increasing order $0
Marcy
  • 629
  • 3
  • 15
1
vote
1 answer

Can you help me to find Omega, Theta, and Big O notations for the following equation?

Can you help me to find Omega, Theta, and Big O notations for the following equation? $T(n)=\left(\frac{n+3}{n}\right)^n$ I have tried this, but I'm unsure if I'm moving in the right direction to solve it. For Big-O notation.. $$0\leq T(n)\leq c…
Aman Rangapur
  • 11
1
vote
1 answer

Big-O analysis of a combination function

Prove that $$\binom{2n}{n} \in O\left(4^n/\sqrt{n}\right) $$ I am not familiar with markdown syntax so sorry for the formula display
Nguyen Hoang Anh
  • 11
1
vote
1 answer

Leading order term of asymptotic expansion

I am trying to find the leading order term in the asymptotic expansion for $$\int_x^1 e^{-1/t} \, dt$$ as $x\to 0^+$. I attempted to do a $u$-substitution by taking $u=\frac{1}{t}$ so $du=-t^{-2} dt$ but then the integral will turn into…
mathim1881
  • 590
  • 2
  • 12
1
vote
1 answer

Asymptotic approximation $I(\lambda) = \int \frac{h(x)}{(h(x) + \lambda |x|^k)^2}\,dx$

Suppose we have the integral $$ I(\lambda) = \int_{-\infty}^\infty \frac{h(x)}{(h(x) + \lambda |x|^k)^2}\,dx,\qquad \lambda > 0, $$ with $h(x)$ the squared modulus of the characteristic function/Fourier transform of a square-integrable probability…
Donkey Fronkey
  • 11
1
vote
2 answers

If $f(n)$ is $O(g(n))$ and $g(n) > 1 + ε$ then $\log(f(n))$ is $O(\log(g(n)))$?

I'm having trouble with the following exercise: Prove that if $f$ and $g$ are positive functions, $f(n)$ is $O(g(n))$ and $g(n) > 1 + ε$ for sufficiently big $n$, then $\log(f(n))$ is $O(\log(g(n)))$. This is what I've done: $f(n)$ is $O(g(n))…
lbal
  • 311
1
vote
2 answers

Division of Big-Theta

In an article about amortized analysis I found an evaluation$$\frac{n\cdot \Theta (1)+\Theta (n)}{n-1}=\Theta (1).$$ I don't really understand how $\Theta (n)$can be divided by $n-1$ as $n-1$ is not a Big-Theta expression, but just a number, and I…
B_Junior
  • 13
1
vote
2 answers

Asymptotic behaviour of $\frac{n^n}{n^n - (n - 1)^n + 1}$ for large $n$

I am interested in the behaviour when $n$ is large of the following function: $$f(n) := \frac{n^n}{n^n - (n - 1)^n + 1}.$$ The limit of this function as $n$ approaches infinity is $$\lim_{n \to \infty} f(n) = \frac{e}{e - 1},$$ where $e$ is Napier's…
user630227
1
vote
0 answers

Little O Rule for sums

To complete a longer a proof I could need a result of the following type: Assume that $m \in \mathbb{N}_{\geq 2}$ is fixed and that we have a sequence $a_k$ with the property $a_k = o(2^{k/m})$ for $k \to \infty$, i.e. $\lim_{k \to \infty}…
Student1369321
  • 145
1
vote
1 answer

Asymptotic expansion of integral - find my mistake

The question asks for the leading term in the asymptotic expansion of $$I(x) = \int_0^{\pi/2} \biggr ( 1-\frac{2t}{\pi} \biggr )^k \cos(x\cos{t}) \, dt, \;\; x \to \infty$$ for $k = 0, -1/2, -3/4$. My attempt: Let $$J(x) = \int_0^{\pi/2} f_k(t)…
Mr_Random_Guy
  • 390
1
vote
1 answer

Does $\log_{2}(n)=\Omega(\sqrt{n})$ imply $n^2 = \Omega(2^n)$?

I'm having some trouble trying to prove $\log_{2}(n) \neq \Omega(\sqrt{n})$. I'm trying to do this without using limits. I am able to prove $n^2 \neq \Omega(2^n)$, so if $\log_{2}(n)=\Omega(\sqrt{n}) \Rightarrow n^2 = \Omega(2^n)$ then I think I can…
mars_plastic
  • 127
1
vote
1 answer

Prove or disprove $n=O(n+n\sin(n))$

So I tried to solve it but got confused because I got weird ressult. $n=O(n+n\sin(n))$ $n≤c(n+n\sin(n)) \quad c=1$ $n≤n+n\sin(n)$ $1≤1+1\sin(n)$ $0≤\sin(n)$ I am wondering am I right to prove that equation or I should disprove it and how to deal…
BMW BOI
  • 23
1
vote
0 answers

Why one can determine$~x^3~$so quickly to remove terms using$~\mathcal{O}(x^3)~$of taylor series of$~\exp(x)~$and absolute symbols can be removed?

Currently I am trying to understand landau big O notation with this post on the wikipedia $$\exp\left(x\right)=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}+\cdot\cdot\cdot~~~~~\text{for…
electrical apprentice
  • 1,519
1
vote
1 answer

Prove or disprove $f(n)\in \omega(log_2(n)) \Rightarrow n\in o(2^{f(n)})$

I can't prove it and I can't disprove it. My try : $f(n)>log_2(n)$ so $\frac {n}{2^{log_2(n)}} \ge \frac {n}{2^{f(n)}}$ $\lim \limits_{n \to \infty} \frac{n}{2^{log_2(n)}}=\lim \limits_{n \to \infty} 1=1$ which means $$0\le \lim \limits_{n \to…
Roach87
  • 696
1 2 3
…
74 75