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

Finding asymptotic expansion

Let $\{ \delta_n (\varepsilon) \}$ be an asymptotic sequence as $\varepsilon \rightarrow 0$, and $a_n$ be independent of $\varepsilon$ and $\delta_n (\varepsilon)$. A series $\sum \limits_{n=0}^{\infty} a_n \delta_n (\varepsilon)$ is said to be an…
snowman
  • 3,733
  • 8
  • 42
  • 73
0
votes
0 answers

Determine orders of equations

$(1)$ Determine the order of the following expressions as $\epsilon \rightarrow 0$ $$(i) \space ln [ 1+\frac{1+2\epsilon}{\epsilon(1-2\epsilon)} ]$$ $$(ii) \space \frac{1-cos \epsilon}{1+cos\epsilon}$$ My attempts: $(1i) =>…
Matt
  • 463
  • 8
  • 17
0
votes
0 answers

Asymptotic behavior of exp(H_n)

I have next problem: $$ e^{H_n} = ... + O(\frac1n)$$ $H_n = \sum_{k=1}^n \frac1k $ I have got the following result: From ($ H_n > \ln n + \gamma $) I go to $e^{H_n} \geq n e^{\gamma}$ Therefore $e^{H_n} = n e^{\gamma} + ... + O(\frac1n)$ What is the…
J.Exactor
  • 215
0
votes
1 answer

How do I find the limit of $8^{\log n}+1+\sin(n)$?

How do I find the limit of $8^{\log n}+1+\sin(n)$ as $n$ goes to infinity? I know that $8^{\log_2n}$ is $n^3$ but $\sin n$ does not exist when you take limit to $\infty$. Can I use L'Hospital's somehow? I can't figure out how to make it a fraction.
yako
  • 311
0
votes
0 answers

Can someone prove that if lim(f(n)/g(n))=0, then O(f(n)) is subset of O(g(n))?

Ah!!!! I got discouraged!! Actually, I asked so many times about this O-notation. Thus, I really wanted to solve myself, but I failed... Is my idea totally wrong to approach the proposition ? $$ if \lim_{n\rightarrow\infty}\frac{f(n)}{g(n)}=0,\…
Danny_Kim
  • 3,423
0
votes
0 answers

Comparing two growth functions

Is $$n\ll\omega(n)\ll n^{1+\epsilon}$$ true at every $\epsilon>0$ where $\omega$ is from Landau notation?
Turbo
  • 6,221
0
votes
0 answers

If $ f = O(g) $ and $ g \notin O(f)$ then $\theta (f) \le \theta (g)$

If $ f = O(g) $ and $ g \notin O(f)$ then $\theta (f) \le \theta (g)$ I've tried to use the definition of $O$ to demonstrate why $\theta (f) \le \theta (g)$ by using the contradiction method but I couldn't. I don't know how to write $g \notin…
asma
  • 1
0
votes
1 answer

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

I know that if f(n) = Θ(g(n)) does that also mean g(n) = Θ(f(n))? but is it true for this case please answer me. I didn't know how to prove it i tried using the definitions but it didn't work i'm i overlooking something
asma
  • 1
0
votes
1 answer

How to formally prove that $f(n)=\Theta f(n+1)$

How to formally prove that $f(n)=\Theta f(n+1)$? It's supposed to be easy, but I still can't get it. Thank you very much.
Talom
  • 1
0
votes
1 answer

How to show $n^k log(n^k) = o(n^{log(n)}) $

Not sure how to show that $n^k log(n^k) = o(n^{log(n)}) $ where $o$ is little-Oh and $k$ is a constant. I mean I really do not know how even to start. Any hints?
YanyongXu
  • 81
0
votes
1 answer

What is correct : $n^{\mathcal{O}(1)} = \mathcal{O}(n^{logn})$ or $n^{\mathcal{O}(1)} = \mathcal{o}(n^{logn})$

I cannot really understand what is right: $$n^{\mathcal{O}(1)} = \mathcal{O}(n^{logn})$$ or $$n^{\mathcal{O}(1)} = \mathcal{o}(n^{logn})$$ I know that Little-oh notation means For every choice of a constant k > 0, you can find a constant a such…
YanyongXu
  • 81
0
votes
0 answers

Proof of asymptotic relation

$$\int ^\pi _0 \frac{\sin(\frac{d k}{2}\cos{\psi})}{\frac{d k}{2}\cos{\psi}}\sin(\psi)e^{-ik\rho\sin(\psi-\alpha)} \, d\psi \sim C \frac{\sin(\frac{d k}{2}\alpha)}{\frac{d k}{2}\alpha}$$ Where $C$ is a complex constant. The relation is valid for…
Gappy Hilmore
  • 3,937
0
votes
1 answer

Big O Notation Proofs Without Concrete Functions

I've looked around for this and I can't find anything close to what I'm looking for. Usually when I saw Big O notation in my classes it was something like: $n^2 + 2n + 1 = O(n^2)$ However, the question I'm being issued now is: If $f(n)$ is…
NotAStudentForReal
  • 109
0
votes
1 answer

Does the fact that $f(n)$ is not $o(g(n))$ and $f(n)$ is not $\omega(g(n))$ imply that $f(n)$ is $\Theta(g(n))$?

Is this statement true? $$f(n) \notin o(g(n))~~~\wedge~~~f(n) \notin \omega(g(n))~~\implies f(n)\in\Theta(g(n))$$ I'm thinking that because $f(n)$ is never greater than or less than $cg(n)$, then it must be growing at the same rate? However I don't…
user274966
0
votes
1 answer

What math symbol can be used to express the same asymptotic order beside the big-Theta?

Suppose $a_n = O(b_n)$ and also $b_n = O(a_n)$. I want to express this but can't use $\Theta$ since it means something else in my report. I'm thinking about this $\approx$, but wondering if there is a better one. I remember seeing a symbol like the…
user262959
  • 141
1 2 3
…
74 75