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

Compare growth rate of functions (exponential vs. polynomial)

I have to compare the growth rate of the following sequences $a_n=a_{n-1}=10$ $b_n=\sum_{k=1}^n k^2$ $c_n =\frac{n^2}{10}$ $d_n=\left( \frac{3}{2} \right)^n$ I've rewritten $b_n$ and $d_n$ to $$b_n = \frac{1}{6} (2n^3+3n^2+n) \quad \text{and}…
Labbiqa
  • 135
2
votes
3 answers

Why is $n \log (n)$ more significant than $n^2 \log (n)$ in terms of efficiency?

I am in a computer algorithms course where I was faced with a problem to determine the big theta efficiency of $n\log(n) + n^2\log(n)$. The solution is $\Theta(n\log(n))$. Why was this chosen over $n^2 \log(n)$?
BrandonW000
  • 21
2
votes
1 answer

Big-O, what do I need the $|x-a|<\delta$ for?

I'm using the following definition for Big-O: $f(x)$ is $O(g(x))$, when $x \rightarrow a$, if $\exists \space M > 0$ and $\delta > 0$ s.t. $|f(x)| \leq M|g(x)|$ when $|x-a| < \delta$ Now for example for the function $f(x)=xsin(x)$ it's easy to…
mavavilj
  • 7,270
2
votes
3 answers

Prove that $\frac{n^2}{2} - 3n = \Theta(n^2)$

The question is, Prove that $\frac{n^2}{2} - 3n = \Theta(n^2)$. I understand that to do this I must determine positive constants $c_1$, $c_2$, and $n_0$ such that $$c_1n^2 \leq \frac{n^2}{2} - 3n \leq c_2n^2$$ I simplified by dividing by $n^2$…
Clark Bell
  • 25
2
votes
1 answer

Little-o vs. asymptotic equivalence

As big- and little-o notation are a little too technical to me, I prefer an expression with asymptotic equivalence ($\sim$). However, how does one "translate" this expression to an asymptotic equivalence? It's about the primorials, as found on…
Jens Bossaert
  • 23
2
votes
0 answers

Local polynomial fitting using Taylor expansion

My question is about the usage of Taylor expansions when dealing with asymptotics in local polynomial fitting. The expressions that set me of are of the type: $$ g(X_i) = \sum_{j=0}^{p} \frac{g^{(j)}(x_0)}{j!}(X_i-x_0)^j…
Hank
2
votes
2 answers

Asymptotic upperbound in multiplication

How can someone calculate the asymptotic upperbound of $2^nn^2$? The first term ($2^n$) grows much faster than the second, but saying that as a final result $2^nn^2 = O(2^n)$ would only be true in the case we had in addition, right? How does it work…
bibliobibuli
  • 23
2
votes
1 answer

Interpretation of $f(n) \in o(n)$

Suppose that some function $f(n)$ is in $o(n)$. Is it fomally correct to say that there exists an $N$ such that for all $n \ge N$ it holds that $$f(n) \le \frac{c n}{g(n)}$$ where $c>0$ is a constant and $g(n)$ is a strictly increasing function of…
somebody
  • 1,085
  • 4
  • 11
  • 19
2
votes
0 answers

Why is $n \exp (-\frac{2m}{n-2}) \ge e^{-w}$?

Here $m=\frac{1}{2}n(\log n + w(n))$. The full claim is that $$\left(1-o(1)\right) n \exp \bigg(-\frac{2m}{n-2}\bigg) \ge (1-o(1)) e^{-w}$$ but am I'm having trouble seeing why. Edit: \begin{align*} \left(1-o(1)\right) n \exp…
Fequish
  • 709
2
votes
2 answers

Big O - equivalent definitions

A function $f(x)$ is $O(g(x))$ if and only if there exists a real number $M$ such that there exists $x_0$ such that for every $x>x_0$ the inequality $|f(x)|\le M|g(x)|$. It turns out the following definition is equivalent to the one…
user5539357
  • 349
2
votes
2 answers

Proof based on definition of big-$O$

I want to prove that $n! = O(n^n)$ based on the definition of big-$O$. I find it pretty easy to show that $n! = O(n^n)$ by simply showing that $n (n-1) < n \cdot n \ldots$ etc. However I can't figure out how to prove this based on the definition of…
crazyGracie
  • 23
2
votes
1 answer

If $f(n)$ and $g(n)$ are both $\Theta (h(n))$ then is it true that $f(n)$ is $\Theta (g(n))$ and $g(n)$ is $\Theta (f(n))$?

My question is exactly what the title says. If two functions are $\Theta$ of another function then are they $\Theta$ of each other. I know that this is not the case with big $O$ but does it work with $\Theta$ because $\Theta$ bounds on both sides?
Nick Chapman
  • 401
2
votes
1 answer

Big O: Trouble finding Witnesses

I am trying to follow this example but I am stumped by where numbers are coming from: Show that $f (x) = x^2 + 2x + 1 $ is $O(x^2). $ The solution is as follows: We observe that we can readily estimate the size of $f (x$) when $x > 1$ because $x <…
tenkii
  • 137
2
votes
2 answers

Laplace's Method to verify an asymptotic approximation

Question: Using Laplace’s method, verify the following asymptotic approximations as $x \to \infty$ $$\int_0^\infty t^x e^{-t} \ln t \, dt \sim \left(\frac{2\pi}{x}\right)^{1/2} e^{-x}$$ I am struggling to get this equation into the form…
Matt
  • 463
  • 8
  • 17
2
votes
0 answers

Watson's Lemma to obtain first three terms

I am unsure how to proceed with the following question due to the fact I am unsure how to obtain a Taylor series for the following function. Question: Using Watson’s Lemma, obtain the first three terms in the asymptotic expansions as x → ∞…
Matt
  • 463
  • 8
  • 17
1 2 3
…
74 75