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
2
votes
0 answers

Question about the $x-[x]-\frac{1}{2}$ term in the derivation of the Euler Summation formula

I am trying to understand why the presence for the $x-\lfloor x\rfloor -\frac{1}{2}$ is needed in the Euler Maclaurin summation formula. I have curated three different sources for the formula's derivation. I came across three different types of…
Seth
  • 3,325
2
votes
2 answers

Little $o$ notation in the exponent

How would you tackle the following expression: $$\phi(x)^{(1+o(1))}=1$$ where $\phi:\mathbb{R}\rightarrow\mathbb{R}^+$ is continuous? $o(1)$ relates to $x\rightarrow\infty$. The specific function is known and I would like to prove the validity of…
user823
  • 335
2
votes
1 answer

How to prove that if $f(x)$ and $g(x)$ have the same asymptotic notation, their integral functions have it too.

How to prove that If $\;f,g:\big[0,+\infty\big)\to\big[0,+\infty\big)\;$ are continuous functions and $\;f(x)=O\big(g(x)\big)\;$ as $\;x\to 0;,\;$ then $\;F(x)=O\big(G(x)\big)\;$ as $\;x\to 0;,$ where $\;\displaystyle F(x)=\int_0^x f(t)dt\;$ and…
whdsm
  • 41
2
votes
1 answer

For every $f(x)$ and $g(x)$: either $g(x)=O(f(x))$ or $f(x)=O(g(x))$

I have the following claim: For every $f(x)$ and $g(x)$: either $g(x)=O(f(x))$ or $f(x)=O(g(x))$. Suppose that the functions are positive, and in addition the relation between them approaches infinity or a constant. My attempt: $Proof.$ Let…
vac132
  • 21
2
votes
1 answer

Big-Oh Notation

I'm given to the following relationship: $$C(x) = C(\lfloor(\frac x2)\rfloor) + x, C(1)=2$$ I do not understand how my teacher says to calculate big O. Any help to start?
user80490
  • 33
2
votes
4 answers

How does one derive $O(n \log{n}) =O(n^2)$?

I was studying time complexity where I found that time complexity for sorting is $O(n\log n)=O(n^2)$. Now, I am confused how they found out the right-hand value. According to this $\log n=n$. So, can anyone tell me how they got that value? Here is…
nikhil
  • 103
2
votes
2 answers

How to determine the leading-order asymptotic behaviour of this integral?

$\int^{1}_{0} \cos(xt^{3})\tan(t)\, dt$ as x → ∞ I am stuck on how to apply the stationary phase method when $\tan(t)$ vanishes at the stationary point. Should I expand tan in its Taylor series? Is the stationary point $0\,$? Thanks in advance
Sanya P
  • 21
2
votes
2 answers

"Big O" notation

To work out the order of a function $f(x)$, I used to just look at the leading term of $f(x)$ (we call $g(x)$) and we would have $\forall x \quad \exists C$ such that $f(x) < Cg(x)$. I was just given the definition: Given two functions $F(t)$ and…
user572780
  • 338
2
votes
4 answers

Asymptote for $y=\frac {x^2}{kx+1}$

We want to find the asymptote of $$y=\frac {x^2}{kx+1}$$ as $x\to \infty$. By synthetic division or binomial expansion, we arrive at $$y=\frac 1k \left(x-\frac 1k\right)$$ which is the correct answer. However we could also have divided top and…
Hypergeometricx
  • 22,657
2
votes
1 answer

chebyshev Inequality, estimator only asyomptotically unbiased

Can I use the chebyshev inequality if my estimator is only asymptotically unbiased? I am trying to show that my estimator converges in probability to $\mu$ if it is asymptotically unbiased and its asymptotical variance is $0$. Many thanks!
Lillys
  • 161
2
votes
2 answers

Asymptotic expansion of an integral as $x \to 0^{+}$

Find the asymptotic expansion of $$F(x) := \int_{x}^{1} \frac{1}{t \sqrt{1+t^2}} \ dt, \text{ as } x \to 0^{+}$$ I tried expanding $\frac{1}{ \sqrt{1+t^2}} = 1 - \frac{t^2}{2} + \frac{3 t^{4}}{8} + \cdot \cdot \cdot$ The integral is then :$$F(x) :=…
Atul Anurag Sharma
  • 652
2
votes
1 answer

Prove that if () = Θ(()), then ln(()) = Θ(ln(()))

Let () and () be asymptotically positive functions, and assume that lim →∞ () = ∞. Prove that if () = Θ(()), then ln(()) = Θ(ln(()))
Justin
  • 21
2
votes
1 answer

Asymptotics of $\frac{n!}{(n- \alpha \log n)!}\left(\frac{c}{n}\right)^{\alpha \log n}$

Let $c > 0$ be some constant, and consider for every positive integer $n$, the function: $$ f_\alpha(n) := \frac{n!}{(n- \lceil{\alpha \log n\rceil})!}\left(\frac{c}{n}\right)^{\alpha \log n}. $$ I would like to determine the smallest…
Drew Brady
  • 3,399
2
votes
1 answer

How to interpret little-o notation in an exponent.

The definition for the little-o notation that I am using is the following: We write $f(n)=o(g(n))$ if $|f(n)|\leq c_ng(n)$, where $(c_n)$ is a sequence such that $c_n\to 0$ as $n\to\infty$. With this in mind, I'm having trouble interpreting the…
user75206
2
votes
2 answers

How can I prove that $x^k = O(k^x)$?

Suppose that k is a constant. I figured out that $k^x \geq x^k$ is true for $x \geq k$. But I couldn't find a way to prove it.
FY Gamer
  • 193
1 2 3
…
74 75