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

Show that $(1 + \mathcal{O}(\epsilon))(1 + \mathcal{O}(\epsilon)) = (1 + \mathcal{O}(\epsilon)) . $

Show that $(1 + \mathcal{O}(\epsilon))(1 + \mathcal{O}(\epsilon)) = (1 + \mathcal{O}(\epsilon)) . $ The precise meaning of this statement is that if $f$ is a function satisfying $f(\epsilon) = (1 + \mathcal{O}(\epsilon))(1 + \mathcal{O}(\epsilon)$…
Jeroen
  • 1,653
2
votes
1 answer

Proving Big O as lim f(n)/g(n) = 0

We have to prove that if $lim_{(n\rightarrow\infty)} \frac{f(n)}{g(n)} = 0$, then $f(n)$ is $O(g(n))$ but $g(n)$ is not $O(f(n))$. I understand that because the limit is 0, then it can be said that $f(n) << g(n)$ (asymptotically smaller) but how…
Matthew
  • 25
2
votes
2 answers

Can $\Theta(f_1) = \Theta(f_2)$?

Does $\Theta(n^3+2n+1) = \Theta(n^3)$ hold? I'm so used to proving that a concrete function is Big-Whatever of another function, but never that Big-Whatever of a function is Big-Whatever of another function.
UnworthyToast
  • 259
2
votes
1 answer

Big-O proof, and the relationship between two different Big-O functions

One question on my homework is as follows: Let $f_1, f_2, f_3, f_4$ be functions from the set $N$ of natural numbers to the set $R$ of real numbers. Suppose that $f_1= O(f_2)$ and $f_3=O(f_4)$. Use the definition of Big Oh given in class to prove…
UnworthyToast
  • 259
2
votes
0 answers

Find an asymptotic upper bound

Use the substistution method to find an asymptotic upper bound for the relation $$T(n)=3 T\left ( \frac{n}{3}+5 \right )+\frac{n}{2}$$ Try so that the bound is as accurate as possible. Consider that the function $T(n)$ is constant for $n \leq…
evinda
  • 7,823
2
votes
1 answer

How to rigorously simplify an expression with Big-Oh Composed within another Big-Oh.

I am trying to show the following: $$ O(e^{n(\cos n^{-2/5}-1)}) = O(e^{-Cn^{1/5}})$$ The problem I'm having is I'm trying to get a hang of asymptotic notation, and I can't quite figure out how to rigorously (in kinda painful detail) to see how to…
MathStudent
  • 1,352
  • 11
  • 22
2
votes
0 answers

Incomplete Beta function $\text{B}_x(\alpha,\beta)$ approximation for large $\alpha,\beta$?

I need good asymptotic approximations to the incomplete Beta function $\text{B}_x(\alpha,\beta)$ for large values of $\alpha,\beta$. Specifically, I need approximations valid for the following regimes: $\alpha > 100, \beta < 100$ $\alpha < 100,…
a06e
  • 6,665
2
votes
4 answers

Proving Big Oh Notation

Show that $f(n) = n^{2} + 2n + 1$ is $O(n^{2})$. Sorry if this is a duplicate question or anything but I'm terribly having a hard time understanding this big-oh notation. I've looked for methods on proving everywhere but I can't seem to understand…
phoenixWright
  • 41
2
votes
3 answers

Proving that $f(x)=2^x$ is $O(x^2)$

Can someone help me with this problem? I don't really know what to do if the x is in exponential form.
phoenixWright
  • 41
2
votes
1 answer

Can the master theorem be applied in this case?

I have to define an asymptotic upper and lower bound of the recursive relation $T(n)=5 T(\frac{n}{5})+\frac{n}{ \lg n}$. I thought that I could use the master theorem,since the recursive relation is of the form $T(n)=aT(\frac{n}{b})+f(n)$ $$a=5…
evinda
  • 7,823
2
votes
2 answers

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

Show that $$\frac{1}{2}n^2-3n=\Theta{(n^2)}$$ $$$$ $\displaystyle{\frac{1}{2}n^2-3n=\Theta{(n^2)}: \\ \exists c_1, c_2 >0 , \ \ \exists n_0 \geq 1 \text{ such that } \forall n \geq n_0 \\ 0
Mary Star
  • 13,956
2
votes
1 answer

How can we show that if $f(n) = O(n^2)$, then $ f(n) = O(n^3)$

I'm looking at the 'positive constants' definition, but just not seeing how to go from here to there.
Steve M
  • 137
  • 3
2
votes
1 answer

Prove that $e^{\sqrt{\log x }}=O(x^n)$

I have to prove the following: Let $n \in \mathbb{N}$. Proove: $$e^{\sqrt{\log x}}=O(x^n) .$$ I just know the definition of $O$: $f(x), g(x)$ are real functions. $f(x)=O(g(x))$ means, that for large $x$, $|f(x)| \leq C \cdot g(x)$ holds. I'm a…
ulead86
  • 3,381
2
votes
1 answer

If $f(n) \in O(g(n))$, then $f(n)+g(n) \in \Theta (g(n))$

I am a total beginner with the big O and big theta notation. How would I prove the following? If $f(n) \in O(g(n))$, then $f(n)+g(n) \in \Theta (g(n))$. I am not sure how to go from the definition of $f(n) \in O(g(n))$. What's confusing me is how…
mitsuki C
  • 21
2
votes
1 answer

Prove or disprove a big o statement

I have to prove or disprove the following statement: $\forall a,b \in \mathbb{R}$, $b > 1$ : $n^a \in O(b^n)$ Clearly there are 2 cases: (i) $a < 0$ and (ii) $a \geq 0$, meaning that I have to prove: (i) $\frac{1}{n^a} \leq c \cdot b^n$ (ii) $ n^a…
tenacious
  • 23
1 2 3
…
74 75