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

Asymptotic growth of $\frac{n}{\phi(n)}$.

I need to prove that for $n \ge 3$ $\frac{n}{\phi(n)}=O(\mathrm{loglog}n)$ But I don't know how to start, I'll be grateful if you could give me some hints. Thanks.
Mugenen
  • 1,091
1
vote
0 answers

I need help to find the asymptotic expansion of the following integral as n approaches infinity.

$ I(n) =\int^\infty_0e^{-\lambda t-n\ln t}\int^\infty_{-\infty}e^{-s^2/2}e^{-i(s/\sigma)\ln t}e^{i(s/\sigma)\ln n}/\Gamma(1+is/\sigma) dsdt $ as $n\rightarrow \infty$, $\lambda >0$ . This is what I did. Change variables $t=nz$, so $dt=ndz$. Thus…
Charles Hagwood
  • 97
  • 3
1
vote
1 answer

Asymptotics of $\sum_{i=0}^{n} \frac{i n^i}{i!}$.

How can you calculate the asymptotics of $\sum_{i=0}^{n} \frac{i n^i}{i!}$ ? This sum looks similar to the power series for $e^n$. I have also seen similar problems solved using Poisson distributions Limit using Poisson distribution for example.…
user66151
1
vote
1 answer

Contributions from all the saddle points or not?

Consider the following integral: $$ I(t)=\int_{\mathbb{R}}e^{itp(z)}dz $$ where $p(z)$ is a real-valued polynomial. And suppose it has both real and non-real critical points, how to find the asymptotics when $t$ goes to positive infinity. Do we only…
DuFong
  • 1,010
1
vote
3 answers

Big-$O$ notation and constant values

Function f(x) $n^3 2^n$ is: a) $O(\ln n)$ b) $O(n^{3 + n})$ c) $O(2^n)$ d) $O (n^3)$ e) None of the above Definition: $f(x)$ is $O(g(x))$ as $x \rightarrow \infty$ if there are positive real constants $C$ and $x_0$ such that $f(x) \leq C g(x)$…
vxbbnm
  • 11
1
vote
2 answers

Which of these function grows faster?

I have the functions $$\frac{n^3}{100000}$$ and $$\frac{n^3}{\log_2(n)}+100n+5000n^2$$ I can't figure out which one grows faster. Can anyone help me?
Boris Grunwald
  • 431
1
vote
1 answer

How to prove anasymptotic equation

How to prove $$\frac{\varTheta(f(n))}{\varTheta(g(n))}=\varTheta\left(\frac{f(n)}{g(n)}\right),$$and does the property still hold for $O$ and $\Omega$ notations? Any answers are appreciated!
J.Butter
  • 11
1
vote
1 answer

Question about asymptotic notation with logs of different bases

For the two functions f(n) and g(n), where $f(n) = n^{1/2}$ and $g(n) = 2^{(\log_2 n)^{1/2}}$, I am trying to determine whether $f$ is asymptotically bound below by $g$, i.e find whether there exists an N1 and a k1 > 0 such that: $ f(n) >= k1 *…
ceno980
  • 469
1
vote
1 answer

Question about Asymptotic Notation

I am doing a question on asymptotic notation. I have two functions $f(n)$ and $g(n)$, where $f(n) = (\log_2n)^2$ and $g(n) = \log_2n^{\log_2n} + 2\log_2n$. I have to determine whether $f(n)$ is $O(g(n))$, $\Omega(g(n))$, or $\Theta(g(n))$. My…
ceno980
  • 469
1
vote
1 answer

Logarithmic asymptotic formula using o(1)

Let's say that we have $\lim\limits_{n\rightarrow\infty} \frac{1}{n}\log a_n \, = \, a$. My professor said that this is equivalent to $a_n \sim \exp(na)$ for $n$ large. Intuitively it makes sense but I cannot really do the algebra to get the result.…
vggls
  • 317
1
vote
1 answer

Asymptotic solution

I am looking for asymptotic solutions to the equation $$\alpha^{-1}x+\sqrt{\pi}\frac{\sqrt{x}}{2}\text{erf}\left(\frac{\sqrt{x}}{2}\right)=\beta^{-1}e^{-x/4},\qquad \alpha\ll1,\beta\gg1.$$ When $\alpha$ is large and the first term is negligible,…
Marc
  • 846
1
vote
1 answer

Can the asymptotic expression $\mathcal{O(log(n) \cdot log(m))}$ be simplified?

I constructed an algorithm $A$ with input $(n,m)$ and I found that it has runtime $\mathcal{O(log(n) \cdot log(m))}$. I was asking myself if this expression can be simplified somehow, but I could not find a way. Do you see a possiblity here?
3nondatur
  • 4,178
1
vote
3 answers

Big Oh-Complexity of $\log(\frac{n}{\log(n)})$ vs $\frac{\sqrt{n}}{\log(\sqrt{n})}$

Could you help me see which of the two functions $f(n) = \log(\frac{n}{\log(n)})$ and $g(n) = \frac{\sqrt{n}}{\log(\sqrt{n})}$ grows asymptotically faster? I would say that $f(n) = \mathcal{O}(g(n))$, since $f(n)$ is logarithmic, but I am struggling…
3nondatur
  • 4,178
1
vote
2 answers

Asymptotics of the integral $\int_0^\pi x^n \sin(x)dx $

I am going through de bruijn's book on asymptotic methods. In the end of a chapter on Laplace's method for integrals, there is an exercise to show the following asymptotic: $$\int_0^\pi x^n\sin(x)dx\sim \frac{\pi^{n+2}}{n^2}, n\to\infty $$ I…
Madarb
  • 583
  • 4
  • 14
1
vote
1 answer

How to multiply using big $O$ notation

Suppose I have the following expression: $$f(n) = \frac{\bigg(1+O(1/n)\bigg)}{\bigg(1+O(1/n)\bigg)\bigg(1+O(1/n)\bigg)}.$$ Is there a way to manipulate $f$ (i.e. multiply by terms involving $n$) in order to get an expression that looks like…
fosho
  • 6,334
1 2 3
…
74 75