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
2 answers

obtain a three-term asymptotic solution

In the limit as $\epsilon \to \infty$, obtain a three-term asymptotic solution to the roots of the following equation. $$\epsilon x^3+x^2-2x+1=0$$ What I've done so far I've assumed $x=O(\epsilon^r)$ as $\epsilon \to \infty$ therefore, $\epsilon…
smith
  • 143
3
votes
0 answers

Manipulating Asymptotic Notation

While looking at the answer key for CLRS Introduction to Algorithm comparing the asymptotic behavior of $f(x) = 2^{(lg*n)}$ and $g(x) =ln(ln (n))$, it states that one can approach this by taking $lg(f(x)) = lg^*(n)$ and $lg(g(x)) = lg(ln(ln(n))$.…
JYCXYZ
  • 115
3
votes
1 answer

Understanding Little Oh Notation Proof - Prove the function$ f(n) = 12n^2 + 6n\ \ is\ \ o(n^3)$

Here is the problem and proof given by my book: Prove the function $f(n) = 12n^{2}+6n$ is o($n^{3}$) Let us first show that $f(n)$ is o($n^{3}$) Let $c \gt 0$ be any constant. If we take $${n_{0}}={{{(12+6)}\over {c}}} ={ {18}\over{c}}$$, then…
yako
  • 311
3
votes
2 answers

Why does 0/0 mean there it a hole and not an asymptote?

https://www.khanacademy.org/math/algebra2/rational-expressions/rational-function-graphing/v/finding-asymptotes-example At around 8 minutes he says that we want a number which makes only the denominator zero, not both the numerator and denominator…
discussedtree
  • 189
3
votes
1 answer

Big-O vs. Best Big-O

Is there a difference between the method to find a big-O function and the method to find the best big-O function. Take for example the following function: $f(n) = 1 + 2 + 3 + ... + n$ It is easy to show that $f(n)$ is $\mathcal{O}(n^2)$ like…
Julia
  • 496
3
votes
1 answer

Big O Notation / landau symbols

I want to write these two in the big O notation: (it's $h\rightarrow0$) $f(h)=\sqrt{h^3}$ $f(h)=h\cdot \log h $ But I don't have any idea how to do this. Thanks for helping!
majorinfo
  • 31
3
votes
3 answers

Show that $2^n=O(n!)$

Show that $2^n=O(n!)$ Proof: By definition of Big-O, $\exists$ constants $c$ and $n_0$ such that $2^n \le cn!$ $\forall $ $n \ge n_0$. For a large $n$, since $$2^n = \underbrace{2 \cdot 2 \cdot 2\cdot\cdot\cdot2}_{n\text{ times}}$$ and $$n! = 1…
Keneth Adrian
  • 1,118
3
votes
1 answer

Show that $\int_{0}^{\infty} e^{ix(\frac{t^3}{3}+t)}dt \sim \frac{i}{x}$

Show that $\int_{0}^{\infty} e^{ix(\frac{t^3}{3}+t)}dt \sim \frac{i}{x}$ I thought that you would use the method of stationary phase, but the maximum of $\frac{t^3}{3}+t$ occurs at $+/- i$. So how do I progress?
Daniel Piggott
  • 75
3
votes
0 answers

Big-O Notation exponentials

I'm learning about Big-O notation for algorithm runtime, and I need some help understanding one part. I read that for the constant, c, does not matter as the function increases rapidly. Does that mean that ?
user237689
  • 31
3
votes
0 answers

Applying function to both sides of asymptotic expression

I apologize in advance if this has been asked elsewhere, but I couldn't find it. This seems like it should be a pretty simple question, but I'm drawing a blank. If you know that $f(x) \sim g(x)$, then under what conditions can you show that…
Lowell
  • 63
3
votes
0 answers

Proof $\mathcal{O}(f(n)) = \mathcal{O}(g(n)) \iff f(n) \in O(g(n)) \land g(n) \in \mathcal{O}(f(n))$

There is an exercise that ask me to prove this logic formula about the complexity of algorithms: $\mathcal{O}(f(n)) = \mathcal{O}(g(n)) \iff f(n) \in O(g(n)) \land g(n) \in \mathcal{O}(f(n))$ Proof: $\mathcal{O}(f(n)) = \mathcal{O}(g(n)) \implies…
user2491173
  • 31
3
votes
3 answers

The order of $\sqrt{\epsilon(1-\epsilon)}$ and $4\pi^2\epsilon$ as $\epsilon \rightarrow 0$?

I was reading on the big O/little O notation etc. and I understand the definitions, but how exactly would I use it to find the order of an expression/function? I am asked to determine the order of $\sqrt{\epsilon(1-\epsilon)}$ and $4\pi^2\epsilon$…
Heijden
  • 31
  • 3
2
votes
0 answers

Difficulty with Asymptotic Expansion of $\int_{0}^{1}\sqrt{t}e^{ixt}dt$

In the book Advanced Mathematical Methods for Scientists and Engineers by Bender and Orszag (question 6.50) we are asked to compute the asymptotic expansion of $\int_{0}^{1}\sqrt{t}e^{ixt}dt$ fully. We are told the answer…
user99163
  • 175
2
votes
1 answer

Problem calculating theta notation

Hello i have to solve the following problem find an $\displaystyle f(k)$ where $\displaystyle S_k=\theta(f(k))$ where $\displaystyle S_k =\sum_{n=1}^{k^2-1} \sqrt{n}$ I tried first of all to calculate or "limit" my sum using integral rule so i came…
ECE
2
votes
1 answer

Bound for sum of products

Given are $x_1,\ldots, x_n\in \{0,1,\ldots,n\}$, $y_1,\ldots, y_n\in \{0,1,\ldots,n\}$ with the property that $$\sum_{i=1}^{n}{x_i}\leq B,$$ $$\sum_{i=1}^{n}{y_i}\leq B$$ Let's assume that $B$ is smaller than $n^2$. This obviously means that if…
user22716
1 2 3
…
74 75