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

Is rearanging allowed when we talk about asymptotic equivalence?

I am examining a certain set of integers, $M$. Let's say, the amount of integers less or equal than $x$ is $S(x)$. Now my studies show that the density of primes in this set $M$ is the double density of primes in the naturals. In…
Lereu
  • 424
0
votes
0 answers

Asymptotics change a lot when adding only a small perturbation

Let $E(p):=\overbrace{(n-2)(\sqrt{2}-2)}^Ap^2+\overbrace{(3n-2)}^Bp\overbrace{-n}^C$, $n\geq 3$ Since $A:=(n-2)(\sqrt{2}-2)$ is negative, the quadratic function $E$ opens downwards, thus when $p
chloe
  • 512
0
votes
0 answers

Show properties of integration of asymptotic relation.

I’m working through Bender and Orzag’s asymptotic methods and perturbation theory and I’m stuck on the following example: Show that if $f(x)\sim a(x-x_o)^{-b}$ as $x\rightarrow x_0+$ then $$\int_x fdx \sim [a/(1-b)](x-x_0)^{1-b}$$ as $x\rightarrow…
LiquidMikerrs
  • 45
0
votes
0 answers

Understanding Asymptotic Equalities

We think about a relation between a function $\psi(x,\epsilon)$ and a divergent power series in $\epsilon$: $f_{0}+\epsilon\,f_{1}+...+\epsilon^{p}f_{p}+...$ The coefficients $f_{0}$, $f_{1}$... can be a function of $x$ only or of $x$ and…
Sylvia
  • 101
0
votes
0 answers

Asymptotic Equivalence on a subset of Natural Numbers

I have a function $f(n)$ defined over $n \in \mathbb{N}$ which I would like to bound asymptotically. I have proven that $f(a) \leq g(a)$ for some subset of naturals $a \in A \subset \mathbb{N}$ and I know $g(n) \sim h(n)$. The function $g(n)$ is…
Ryan Farrell
  • 1
  • 1
0
votes
0 answers

Steepest descent method asymptotic function

I want to compute the asymptotics of \begin{align*} \mathrm{AI}(x) = \frac{1}{2 \pi i} \int_C e^{i z x + i z^3/3} \frac{ dz}{z}, \quad x \in \mathbb R, \end{align*} as $x \to \pm \infty$. Here $C$ is a contour in the upper-half of the complex…
hanamontana
  • 333
0
votes
0 answers

Big-oh of non-polynomial functions

I am struggling on some problems asking me to prove that one function is Big-Oh of another function, but these functions are a little more complicated than the typical examples seen in practice. For example, Prove $(\log n)^3 \in O(\sqrt{n})$ I know…
Matthew Kaplan
  • 105
  • 7
0
votes
1 answer

BigO of functions with subtractions

I have $f(a, b) \in O(b - a)$ and $g(a) \in O(a)$. Can I conclude that $f(a,b) + g(a) \in O(b)$? What if $f(a, b) \in \Theta(b - a)$ and $g(a) \in \Theta(a)$?
scand1sk
  • 323
0
votes
2 answers

Big O notation question: $\exp(-\frac{x^2}{2} + x) = O(\exp(-\frac{x^2}{2}))$ true?

From the definition of the big O notation, since $-\frac{x^2}{2} + x < -(1-\epsilon)\frac{x^2}{2}$ for large $x$ and for any positive $\epsilon > 0$, I think $\exp(-\frac{x^2}{2} + x) = O(\exp(-(1-\epsilon)\frac{x^2}{2}))$ is valid. My question is…
mike
  • 43
0
votes
0 answers

Find second order asymptotic approximations of solutions of non-linear equations

To compute asymptotic approximations of solutions $u(x,y),v(x,y)$ of the system of equations \begin{cases} u^a+v^b+x+y= 4\\ u+v+x+y= 4 \end{cases} near $(u,v)=(1,1),(x,y)=(1,1)$. I replace $u^a$ by $1+a(u-1)$, similarly for $v^b$, I get a linear…
hbghlyj
  • 2,115
0
votes
0 answers

What does big Omega imply about big O? And how does $f(n)=\Omega(n)$ imply cannot be bounded by a constant?

I'm trying to figure out the implications of $\Omega$ in asymptotic analysis. Let's say I have a function $f(n)=\Omega(n)$. From my understanding, and Asymptotic analysis: difference between big O and big Omega limits? this implies the…
somewhere
  • 69
0
votes
2 answers

Prove or disprove: $\log_{\cos(\frac{\pi}{n})} (\frac{1}{e})= \Theta(n^2)$

As titled, I want to prove (or disprove) $\log_{\cos(\frac{\pi}{n})} (\frac{1}{e})= \Theta(n^2)$. It seems to be true by plotting this function. However, I do not know how to make use of the $\cos(\frac{\pi}{n})$ to show the function is indeed…
William Zheng
  • 428
0
votes
0 answers

Struggling with Algorithmic Inequalities - Seeking Insights and Feedback on Approach!

Hello everyone I don't really understand the question. I approached the given problem by carefully examining the provided sequence of inequalities, aiming to understand the growth rates of various functions. Breaking down the given function (f(n) =…
Orzibekov Yusufbek
  • 1
0
votes
1 answer

Show if $f(n)$ has polynomial growth and $g(n)=\Theta(f(n))$, then $g(n)$ also has polynomial growth

As stated in the question title, if $f(n)$ has polynomial growth and $g(n)=\Theta(f(n))$, then how can we show $g(n)$ also has polynomial growth? $g(n)=\Theta(f(n))$ gives us $0\leq c_1f(n)\leq g(n)\leq c_2f(n)$ for some positive constants $c_1,…
Mason Rashford
  • 489
0
votes
3 answers

$c^3 \ll l^3$ prove that $\sqrt{l\over{l+c}}+\sqrt{l \over{l-c}}=2+{3c^2\over 4l^2} $

If $c^3$ is negligible compared to $l^3$, how may I prove that $$\sqrt{l\over{l+c}}+\sqrt{l \over{l-c}}=2+{3c^2\over 4l^2}?$$ This might be a problem involving binomial series.
DebojyotiMukh
  • 915
1 2 3
…
74 75