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

If f(n) = Θ(g(n)) does that also mean g(n) = Θ(f(n))?

I'm fairly certain that if f(n) = Θ(g(n)) is true, g(n) = Θ(f(n)) must also be true. However, I'm concerned I might be overlooking something. Am I correct in thinking that f(n) = Θ(g(n)) then g(n) = Θ(f(n))? or am I overlooking something?
Wipqozn
  • 135
3
votes
5 answers

Is $n! = o(n^n)$?

Intuitively, it seems that $n! = o(n^n)$. We can associate each value in the factorial with a single $n$ to divide by, so $\lim_{n \rightarrow \infty} \frac{n!}{n^n}$ seems to be $0$. However, I think I have encountered a contradiction. It turns out…
David Faux
  • 3,425
3
votes
1 answer

Can we do asymptotic calculation like this?

If we know $$ E(Z_i) = H_i + H_{n - i + 1} - 2 $$ and $i \sim \sqrt n$. Can we write: \begin{align*} E(Z_i) & = H_i + H_{n-i+1} - 2 \\ & \sim \log i + \log (n-i+1) \\ & \sim \log \sqrt n + \log n \\ & \sim \frac 3 2 \log…
NonalcoholicBeer
  • 7,211
3
votes
1 answer

Asymptotic behaviour of e * !n - n! , n tends to infinity

What is the asymptotic behaviour of the function $e !n-n!$ , where $!n = n! \sum_{k=0}^n \frac{(-1)^k}{k!}$ is the subfactorial of $n$. I tried Wolfram Alpha but the series for n=$\infty$ is pretty complicated. There should be a simplier…
Peter
  • 84,454
3
votes
1 answer

How to find $\frac{n^3}{1000} - 100n^2 - 100n + 3$ in terms of Θ and prove it?

Question: Express the function $\frac{n^3}{1000} - 100n^2 - 100n + 3$ in terms of the Θ notation and prove that your expression in fact fits into the Θ definition. So far I have, $n^3 / 1000 - 100n^2 - 100n + 3 = Θ(n^3)$ $f(n) = n^3 / 1000 - 100n^2…
Auxiliary Soap
  • 33
3
votes
1 answer

Runtime Analysis, Coefficients in logarithms? Ignorable?

I had a question regarding when we can ignore constants during Big O analysis. If I had $f(n)=\log5x$ and $g(n)=\log100x$, would the constants $5$ and $100$ be ignorable when considering $n \to \infty$, such that $f(n) = \theta(g(n))$? Conceptually,…
TheoretiCAL
  • 185
  • 5
3
votes
1 answer

Can anyone derive the formula for the expansion $(x + \Delta x)^{n}$ that uses Big O notation?

There is a formula that describes this expansion using big O notation, I'm very curious on how this is derived. I also understand that the order term may very depending on what $\Delta x$ approaches to in limit ? $(x + \Delta x)^{n} = x^{n} +…
Amber Roxanna
  • 189
3
votes
1 answer

Discovering Appropriate Bounds in Multivariable Asymptotics

I am having some difficulty with multivariable asymptotics. Let me provide a concrete example of the kind of thing I mean. Stirling's approximation for $n!$ is $$ n! \sim \sqrt{2 \pi n}\left( \frac{n}{e} \right)^n. $$ For ease of notation, denote…
Austin Mohr
  • 25,662
3
votes
2 answers

Number of smooth numbers less than x

A $p$-smooth number is defined as an integer whose prime factors are all less than or equal to $p$ In the wiki article about smooth numbers it states: Let $\displaystyle \Psi (x,y)$ denote the number of $y$-smooth integers less than or equal to $x$…
Kinheadpump
  • 1,331
3
votes
1 answer

$f(n) = O(g(n))$ implies $g(n) = O(f(n))$

How do I prove/disprove $f(n) = O(g(n))$ implies $g(n) = O(f(n))$? I got to $f(n) \le c * g(n)$ easily enough from the definition of Big O, but I'm not sure how to get to $c*f(n) \ge g(n)$.
too careful
  • 133
3
votes
2 answers

Asymptotic expression for discrete random walk

I am trying to approximate the evolution of probability distribution of discrete random walk on the integers, starting from zero at the time step $n=0$. The probability of being at integer $k$ at time step $n$ is given by $$P_k(n)={1\over 2^n}…
Atom
  • 3,905
3
votes
2 answers

$n^{2/3}$ dominates $n^{1/2}$, what would be the correct big O/Theta/Omega?

If I have $f(n)=n^{2/3}$ and $g(n) = n^{1/2}$, then I believe their big $O$'s are $O(n^{2/3})$ and $O(n^{1/2})$. This is where I'm a little confused. I need to find if $f=O(g)$, $f=\Omega(g)$ or $f=\Theta(g)$. I know that $f$ dominates $g$, so they…
Grav
  • 133
3
votes
2 answers

Find the leading order of the integral $\int_0^1 \cos\left(x{t^4}\right)\tan t\,dt$, while $x$ goes to $+\infty$.

I would like some help with this problem. I don't know where to start. Is it right to try integration by parts? Another method that I've learned is to find the Taylor series of each function and then integrate. But I am not sure if this is the right…
Truth Hunt3r
  • 33
  • 2
3
votes
2 answers

asymptotics of $\sum_{n=0}^\infty x^{n^2}$ as $x\rightarrow 1$

This is an exercise in the book by Titchmarsh, 'the theory of functions', page 242. The answer is $\frac{1}{2}\sqrt{\pi /(1-x )} $. How to prove it? It is a little bit surprising to me. The function $1/\sqrt{1-x} $ has a quite different Taylor…
S. Kohn
  • 1,084
3
votes
0 answers

Is $O(f(n)\cdot g(n)) = f(n)\cdot O(g(n))$?

Prove or disprove with counter example: $$O(f(n)\cdot g(n)) = f(n)\cdot O(g(n))$$ Attempt: $f(n) = x^2 + x + 1$ $g(n) = x^3$ L.H.S. = $x^5$ R.H.S. = $(x^2 + x + 1)x^3$ L.H.S. $\neq$ R.H.S. Am i correct?
kayush
  • 2,441
1 2 3
…
74 75