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

finding order of exponential boundary function

The $L_p$ norm $\|e^{-x/\epsilon}\|_p=(\frac{\epsilon}{p})^{1/p}(1-e^{-p/\epsilon})^{1/p}$, $1\leq p<\infty$ on the interval $(0,1)$. I am not sure why this norm is $O(\epsilon^{1/p})$ as $\epsilon$ approaches 0. Is it because as $\epsilon$…
Vaolter
  • 1,711
0
votes
0 answers

Understanding $a^a=n$

I have been looking at a particular computational problem and finally reduced it down to a bound of $a^a=n$, I will try to explain what I mean by this first in one paragraph. For example, suppose I am trying to find if an element exists in a sorted…
User Not Found
  • 962
0
votes
0 answers

Notation in asymptotic formulas

I have a rather trivial question regarding the notation connected with simple asymptotic formulas. Let the solutions of an equation asymptotically be given by $$z_n=iy^2_n+O\,(1/y^2_n),\quad |n|\rightarrow\infty,$$ where $$y_n=(n+1)\pi,\quad…
Trevor3
  • 147
0
votes
1 answer

big O inequality

In $e^{-\omega/\epsilon}\leq10^{-9}$ why is $\omega=O(\epsilon)$ and in $e^{-\omega/\epsilon}\leq \epsilon$ why is $\omega=O(\epsilon\ln1/\epsilon)$ where $\epsilon$ is a very small parameter.
Vaolter
  • 1,711
0
votes
1 answer

Proof of $n^k \ll (1 + \epsilon)^n$ from Spencer's Asymptopia book

I intuitively understand $n^{k} \ll (1 + \epsilon)^n$ however the logic of the proof I don't understand, from the chapter on the hierarchy of standard form functions in the book: Proof. First set $f(n) = n^k$, $g(n) = (1 + \epsilon)^n$. We compare…
JJbh
  • 3
0
votes
1 answer

why does the h in Torricelli's law (the form that relates height to time) go to zero rapidly?

https://class.coursera.org/calcsing-002/lecture/320 In the the above linked lecture at 5:44, we are trying to find how fast liquid leaks from a cone shaped tank. I understand the derivation but at the end it mentions that $h$, which is in $\mathcal…
maogenc
  • 1,165
0
votes
2 answers

Is it possible for a function(f) to be $O(f)$ but not $o(f)$?

Is it possible for a function(f) to be $O(f)$ but not $o(f)$? or $o(f)$ but not $O(f)$? I guess it might be possible for a function that is not monotonically increasing. Is there an example of this case? Added: Is it correct if I say subtracting …
user84058
  • 11
0
votes
1 answer

May I know if these big-O's are correct?

Some exercises for myself, (1) $ln((1+\frac{1}{n})^n) \sim 1$ so $ln((1+1/n)^n)=1+o(1)$ as $n \rightarrow \infty$? (2) $(1+o(1)) ln(n+1) + o(n^2)=1+ln(n+1)+o(n^2)$ (3) $(f(n)+o(n^2))^k = \sum_{i=0}^{k} \binom{k}{i} f^{k-i}(n)o(n^{2i}) $ Can it be…
LLT
  • 5
0
votes
1 answer

Questions on small O notation

I am trying to understand the small o notation and have come up the below exercises. Are they correct, as $n\rightarrow \infty $? (1) $(n+1)/n=1+o(1/n)$ (2) $log(n+1)=log(n)+o(1/n)$ (3) $nlog(n)+nlog(log(n))=nlog(n)+o(n)$ (4) $o(n)o(1/n)=o(1)$,…
LLT
  • 5
0
votes
1 answer

Prove or disprove $\forall a\in \mathbb{N} : \log_2(n)^a = o(\sqrt{n})$

I tried finding a few inequalities but all didn't seem to get me anywhere. My try: By $\log(x)
Roach87
  • 696
0
votes
0 answers

1. Prove or disprove that $\log_{10}{\sqrt{n}} = \Theta(\lg{n^{5}})$ 2. Prove or disprove that $4\log_{10}{n}=O(\sqrt{n}\lg{n^{3}})$.

Prove or disprove that $\log_{10}{\sqrt{n}} = \Theta(\lg{n^{5}})$ Prove or disprove that $4^{\log_{10}{n}}=O(\sqrt{n}\lg{n^{3}})$. For the first question, I divide $\lg{n^{5}}$ on both side and find that $$\frac{\log_{10}{\sqrt{n}}}{\lg{n^{5}}} =…
Ni Jiasheng
  • 11
0
votes
2 answers

Confused on Asymptotic equality between a sum and integral

I'm currently reading through Chapter 10 of the book The Cauchy-Schwarz Master Class. I'm stuck on this step that they use to prove what they call the Double Sum Lemma: Double Sum Lemma $$ \sum_{m=1}^\infty \sum_{n=1}^\infty \frac1{n^{\frac12 +…
eeen
  • 889
0
votes
0 answers

Can anyone confirm this operation with big $O$

I do not know if it is the usual type of question to ask for someone to confirm a computation, but I don't really have any way to know if this is correct (or do I?). Lemma A function $f: \mathbb{N} \to \mathbb{C}$ verifies $$f(n) \leq…
Macarena Perelman
  • 73
0
votes
2 answers

Big-O Asymptotical Dominance and its Constants

I keep reading that a function $g(n)$ dominates a function $f(n)$ if there are constants $K$ and $L$ where: $K \cdot g(n) \ge f(n)$ whenever $n \ge L$ My confusion is in the finding values for those constants. How do you find fitting values to these…
FoxVocs
  • 3
0
votes
1 answer

Big O boundary condition truth value

Note: logs below are base 2. (Not sure how to do subscripts here) Wondering if the below equation is true when thinking asymptotically (Computer Science) $log_2((n!)^n) = O(n \sin(n \frac{\pi}{2}) + \log_2{n})$ But I'm not sure how to compute…
Sev
  • 2,093
1 2 3
…
74 75