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

A confusion about big Oh notation

As far as I know, the statement $|T|\le C_M\cdot (\log N)^{-1}.|\Omega|,\ (C_M>0)$ should imply that $$|\Omega|=\mathcal{\Omega}(|T|\log N)$$ but this seminal paper by Candes et al. says in the abstract that $|\Omega|=\mathcal{O}(|T|\log N)$. I am…
Samrat Mukhopadhyay
  • 16,277
2
votes
0 answers

Big $O$ notation clarification

I've encountered something of the form: $$f(n)O(g(n))$$ I think this is equivalent to $O(g(n)f(n))$, but is this true?
ernie
  • 21
2
votes
0 answers

Asymptotic expansion of $x_{n}$, $x_{n}=\frac{1}{\tan(x_{n})}$

I would like to find a two-term or a three-term asymptotic expansion of $x_{n}$ the unique solution of $$x_{n}=\frac{1}{\tan(x_{n})}$$ on the interval $]n\pi,n\pi+\pi[ $ We have: $$ x_{n}=n\pi+\arctan(\frac{1}{x_{n}})$$ So $$x_{n} \sim_{n\rightarrow…
Chon
  • 6,002
2
votes
2 answers

asymptotic expansion from 3 leading terms

The function $w(x)$ satisfies $$\frac{d^2w}{dx^2} + 2x\frac{dw}{dx} - 2\beta w = 0$$ with $$w(\infty)=0 \text{ and } 0<\beta < 1.$$ By writing $w(x)= exp(-x^2)f(x)$, obtain the first two terms of an asymptotic expansion for $w(x)$ as $x \to \infty…
smith
  • 143
2
votes
0 answers

How to prove the following conjecture.

Prove if $d(n)$ is $O(f(n))$ and $e(n)$ is $O(g(n))$, then $d(n) + e(n)$ is $O((f(n) + g(n)))$. What I tried. if $d(n)$ is $O(f(n))$ then $d(n) \leq c_1 \cdot f(n)$ if $e(n)$ is $O(g(n))$ then $e(n) \leq c_2 \cdot f(n)$ which implies $d(n) + e(n)…
Rohit Kumar
  • 157
2
votes
2 answers

oblique asymptote problem

I can't resolve limit for oblique asymptote for: $$\frac{2x^2 e^{1/x}}{2x+1}-x$$ I've tried solving it by putting the common denominator but it's a bit confusing because the numerator is bigger then the denominator....
Anthony
  • 93
2
votes
2 answers

Which of these two functions grow asymptotically faster?

Which of these two functions grow asymptotically faster? $$2^{\sqrt{\log^{1.9}n}}$$ $$n^{1/5}$$ I think the answer should be $2^{\sqrt{\log^{1.9}n}}$. I made an excel spreadsheet with both these functions and the first one goes higher, quicker. Is…
Julia
  • 496
2
votes
1 answer

Growth analysis: fractional power functions dominate polylogarithmic?

In big-O notation for algorithmic time-complexity analysis, given real-valued functions $f$ and $g$, $f(x)$ is $O(g(x))$ if there are constants $C$ and $k$ such that $$ |f(x)| \leq C |g(x)| \quad \forall x > k $$ I'm struggling with the case $f(x) =…
Karmen
  • 121
  • 2
2
votes
1 answer

Big-O notaion for $2n^4 + \log_2n^8$

I need to find the best big-O for: $$3n^4 + \log_2n^8$$ So I said: $$3n^4 + \log_2n^8 = 3n^4 + 8\log_2n \leq 3n^4 + 8n$$ Therefore, the given function is $O(n^4)$ in the best case. Is this correct?
Julia
  • 496
2
votes
1 answer

Is $\sqrt{2/(27\pi n)}\sim n^{-1/2}$?

Is $\sqrt{2/(27\pi n)}\sim n^{-1/2}$? Since $$ \sqrt{\frac{2}{27\pi n}}=\sqrt{\frac{2}{27\pi}}\cdot\frac{1}{\sqrt{n}}\sim\frac{1}{\sqrt{n}}=n^{-1/2}, $$ I would say, yes, of course.
Salamo
  • 1,094
2
votes
1 answer

Big O notation - Asymptotics - Question

I want to prove the following$$n - 2\sqrt{n} = \Theta(n)$$ Is it correct to say $$n -1 \leq n \leq n +1 => f(n)=n=\Theta(n)$$ $$\sqrt{n}\leq|-2\sqrt{n}| = 2\sqrt{n}\leq3\sqrt{n} =>g(n)=-2\sqrt{n}=O\sqrt{n}$$ So:     $n - 2\sqrt{n} =…
user248445
  • 53
2
votes
2 answers

Unusual Asymptotics Question

I want to prove the following$$n - 2\sqrt{n} = \Theta(n)$$ Is it correct to say $$n -1 \leq n \leq n +1 => f(n)=n=\Theta(n)$$ $$\sqrt{n}\leq|-2\sqrt{n}| = 2\sqrt{n}\leq3\sqrt{n} =>g(n)=-2\sqrt{n}=O\sqrt{n}$$ So:     $n - 2\sqrt{n} =…
user248445
  • 53
2
votes
1 answer

True or false. If $f(n) = \Theta(n^2)$ and $g(n) = \Theta(n^2)$ then $(f-g)(n) =\Theta(n^4)$ where we define $(f-g)(n)=f(n)-g(n) \forall n$.

True or false. If $f(n) = \Theta(n^2)$ and $g(n) = \Theta(n^2)$ then $(f-g)(n) =\Theta(n^4)$ where we define $(f-g)(n)=f(n)-g(n) \forall n$. I believe this is false. Take $f(n) = 4n^2, g(n) = 2n^2$. Then $f(n)-g(n) = 2n^2$ and $2n^2$ is not…
User
  • 907
2
votes
1 answer

Using $f=O(g)$ to compare $f^2$ and $g^2$

When we have $f = O(g)$, does this work? $f^2 = O(g^2)$? If I have $n^2 = O(n^3)$, I think that $n^4= O(n^6)$ so I think this is valid. What about $2^f vs 2^g$? Does $f = O(g)$ imply $2^f = O(2^g)$? And also can I do this? if $f = θ(g)$, is $f^2 =…
maregor
  • 235
2
votes
2 answers

Order estimates question and big O notation

How can I show that $y(x) = 1 - \cos(x)$ is $\mathcal{O}(x^2)$ for $|x| <<1$ ? Additionally, with the $|x| << 1$ is there a precise definition? I tried to google it but nothing conclusive returned. I'm assuming it just means $x \to 0$. Is there any…
elbarto
  • 3,356
1 2 3
…
74 75