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
1 answer

Simple Asymptotic Question

I was wondering if someone could help me figure out the asymptotic of $(1 + x)^{1/k}$, where $x$ is going to $0$ and $k$ is a fixed positive integer. I know it is going to 1, but I wanted to know the second term and the O-bound if possible. Thank…
J Kasahara
  • 273
1
vote
0 answers

Polynomial time for a graph algorithm

Suppose an algorithm $A$ which, given a graph $G$ on $n$ vertices (represented in, say, adjacency matrix form) and some parameter $C$, runs in time $T = O\bigl(n^2\cdot \sqrt{C}\bigr)$. Is the algorithm taking polynomial time or pseudo polynomial…
zigtones
  • 11
1
vote
1 answer

Asymptotic solutions of trascendental equations

Consider the equation $$\beta x\text{erf}(x)=\frac{1}{\sqrt{\pi}}\exp(-x^2),$$ where $\beta\ll1$ and $$\text{erf}(x)=\frac{2}{\sqrt{\pi}}\int_0^xe^{-t^2}\text{d}t$$ is the error function. I am looking for an approximate solution of the form…
Marc
  • 846
1
vote
1 answer

Show something has a linear asymptote

Consider the function $z(x)=\sqrt{1+x^2}+1$ Show that $y=x+1$ and $y=1-x$ are linear asymptotes of the function at $\infty$ and respectively $- \infty$ So I started of with the first part: show that $y=x+1$ is a linear asymptote of the function at…
Bob
  • 869
1
vote
1 answer

Is there a systematic way of determining the "correct" asymptotic approximation?

Consider these two quadratic equations, $$\text{i)} \quad x^2+4x-5-\epsilon$$ $$\text{ii)} \quad \quad x^2+(4+\epsilon)x+4-\epsilon = 0$$ If we attempt to find an asymptotic approximation of the form $$x = x_0 + \epsilon x_1+...$$ for i) this works…
user197848
1
vote
1 answer

Asymptotic Expansion of $\displaystyle\int_0^{\pi/2}e^{-z\sin^2(t)} \, dt$

I want to find the asymptotic expansion of $$\int_0^{\pi/2}e^{-z\sin^2(t)} \, dt$$ As I need to find the entire asymptotic expansion (and not just the first term or two), it suggests I don't want to use Laplace's method (at least not on its…
user112495
  • 384
  • 4
  • 13
1
vote
1 answer

Asymptotic expansion of $\cos x $

I want to determine whether or not $\cos x$ has an asymptotic expansion of the form $\sum_{k=0}^{\infty} \frac{a_k}{x^k}$ as $x \to \infty$ in $\mathbb{R^+}$. This means we are taking the asymptotic series $\psi_k(x) = x^{-k}$, but I don't really…
user112495
  • 384
  • 4
  • 13
1
vote
0 answers

How is dropping $S''$ compared to $(S')^2$ justified in the method of dominant balance?

Consider an equation like $$y''(x)+y'(x)-xy(x)=0.\tag1$$ Using method of dominant balance, we substitute $y(x)=e^{S(x)}$ and get $$S''(x)+(S'(x))^2+S'(x)-x=0.\tag2$$ Now we assume that $S''(x)\ll (S'(x))^2$ as $x\to\infty$ and then…
Ruslan
  • 6,775
1
vote
2 answers

Can Watson's Lemma be applied on multiple integrals simultaneously?

I need to calculate the asymptotics of the integral $$\left(\int_0^1 \mathrm e^{-tx} f(t)\right)^j$$ for $x\to\infty$. I suspect (and would like to prove), that this behaves like $$\left(\sum_{n=0}^{\infty}…
filmor
  • 541
1
vote
1 answer

Prove that $\log(n^n)=\Theta(\log(n!))$

I'm having problem proving that $\log(n^n)=\Theta(\log(n!))$ I tried to use Stirling's formula but it seems it doesn't help me in this case. This is what I wrote : $$n \to \infty : \frac{\log(n!)}{\log(n^n)}=\frac{\log(\frac{\sqrt {2\pi n}}{e^n…
Paolo Molina
  • 289
1
vote
1 answer

Little O Computation: $4n\:\in \:o\left(n^2\right)$

For this, I know you can use calculus techniques and set $\lim _{x\to \infty }\left(\frac{4n}{n^2}\right)$ and get 0. Though, I'm wanting to know how you can get a specific constant and k values.
user372522
1
vote
3 answers

Proving Big-O notation

I need to prove, that $5n^2+7=O(2^n)$ I came up with the following proof, is this correct? To prove this, we need to show $5n^2+7 \le c*2^n$ for $n \ge b$ We know, that $7\le n^2$ for ever $n\ge3$ (Can we just assume this or do we have to prove…
Bowueewa
  • 25
  • 1
  • 3
1
vote
1 answer

Big O definition and showing equality

On this problem, I'm not sure what Big O definition they are referring. How would the big o definition help show this? Use the definition of $O$ to show that if $y = y_h + O(h^p)$, then $hy = hy_h + O(h^{p+1})$.
john
  • 21
  • 3
1
vote
0 answers

Is $O(n/\log(n/m))=O(n/\log(n))$ when $1 \leq m=o(n)$?

Question: Is $$O\left(\frac{n}{\log(n/m)}\right)=O\left(\frac{n}{\log n}\right)$$ when $1 \leq m=o(n)$? It would be true when $m \leq k n^\varepsilon$ for any fixed $\varepsilon < 1$ and constant $k$, since then we have $$\log (n/m) \geq \log(n/(k…
Rebecca J. Stones
  • 26,845
1
vote
1 answer

Proving that O(max(g(x), f(x))) is in O(g(n) + f(n))

I was hoping that someone could verify that my proof is correct. Okay, here we go. $$max(g(n), f(n)) \le 1(g(x) + f(x)) \text{ for all x > 0} $$ $$\text{Let A = 1 and }n_0 = 1$$ $$max(g(n), f(n)) \le A(g(x) + f(x)) \text{ for all n >=}n_0 $$ by…
T-bone's House
  • 63
  • 2
  • 8
1 2 3
…
74 75