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

Horizontal asymtote with vertical asymtotes

I did quite a bit of research before getting stuck here. So I have a function: $\frac{e^x}{cos(x)}$ A vertical asymptote occurs every $n\pi+\frac{\pi}{2}$ I believe (as the denominator approaches 0), but we also have $\lim_{x\to -\infty} e^x = 0$…
J-Dilla
  • 21
2
votes
1 answer

"$f$ is asymptotically greater than $g$"

What's the notation for ranking functions in increasing asymptotic order? I saw a notation with $\prec$ earlier, but now I can't find it. Would the following notation be correct? $$\mathcal{O}(n)\prec \mathcal{O}(n\log n)$$
Steve
  • 179
2
votes
1 answer

Asympototic solution

Asked to find first three terms in the local behavior as $x\to 0^+$ of the solutions of $\displaystyle{y'+ xy = \frac{1}{x^3}}$ This was taken by bender and orszag book Working : I tried to use method of dominance but later realised that we can…
XXXXX
  • 23
2
votes
1 answer

Multivariable Asymptotics: Show that Θ(x^3 + xy + y^2) = Θ(x^3 + y^2)

Problem: Show that for positive integer values of x and y, $$Θ(x^3 + xy + y^2) = Θ(x^3 + y^2)$$ Solution: For this specific example, I can show that $xy$ is asymptotically dominated by the other terms by checking two different cases: $$x >y…
Otay
  • 91
  • 9
2
votes
1 answer

Proving that $\log_d(n) \in \Theta(\log_2(n))$

I'm supposed to prove the theorem below either by definition or the limit test. I understand both of these methods but I'm having a hard time applying them to this particular theorem. $d > 1, \log_d(n) \in \Theta(\log_2(n))$ I know that by…
Jasmine
  • 67
2
votes
1 answer

Big O on $(1.0001)^n$ $n^{1.0001}$ and $2^\sqrt{logn}$ vs $1.0001^n$

It's been a while since I touched limits/calculus so I'm a little iffy on the problem below. Given the two sequences $(1.0001)^n$ $n^{1.0001}$ which one grows faster? My reasoning is that $(1.0001)^n$ or aka 1.0001 multiplied to itself n times…
learning7
  • 23
  • 3
2
votes
2 answers

Understanding big O notation based on the examples given

I have some questions about the examples I came by in a book that helps me to explore the world of programming. I understand what Big-O notation is and interested in the following: 1. To prove if $g(n) \in O(f)$, everything we need is to find only…
Dmitrii
  • 123
  • 2
2
votes
2 answers

Asymptotic for implicitly given function

Function $n(s)$ is given implicitly as $n! = s$. How can I find an asymptotic for $n(s)$? I cannot understand, how can I make an explicit function from this to calculate an asymptotic, as there is no reverse operation for factorial (I mean, like…
Kos
  • 255
2
votes
1 answer

Any way to show that $\Theta(\sum_{i = 1}^n f(i)) = \Theta(n f(n))$?

Given some monotonically growing function, is there any way to show that $\Theta(\sum_\limits{i = 1}^{n}f(i)) = \Theta(nf(n))$? I know for a fact that this holds for the identity function $f(n) = n$. Indeed: $\sum_\limits{i = 1}^n i = n(n + 1)/2$.…
Sal Rahman
  • 244
2
votes
1 answer

finding leading behavior of a differential equation

we have $$ y'' = \sqrt{x} y $$ I want to find the leading asymptotic behavior as $x \to \infty$ I tried substituting $y = e^{S(x)}$ and then after obtaining $S(x) \sim \pm \frac{4}{3} x^{3/4} $ and doing the correction $S = \pm \frac{4}{3} x^{3/4}…
user139708
2
votes
1 answer

Code Run Time Proof

TRUE or FALSE: For two positive functions $f(n)$ and $g(n)$, $f(n)$ has to be either $O(g(n))$ or $\Omega(g(n))$ or both. I feel like using $\sin$/$\cos$ for $f$ and $g$ would be a way of showing this is false, but I don't understand how to…
John
  • 23
2
votes
4 answers

Asymptote to the curve $y= \dfrac {3x}{2}\log\left(\mathrm e-\frac{1}{3x}\right)$

$$y= \dfrac {3x}{2}\log\left(\mathrm e-\frac{1}{3x}\right)$$ We have to find the asymptote to the curve I tried solving the problem by taking its limit as $x$ tends to infinity. But I failed. Can anyone help.
Navin
  • 2,605
2
votes
2 answers

A function that is neither O(n) nor Ω(n).

I think I have a function like this, $$f(n) = (1 + \sin n) \cdot 2^{2^{n+2}}.$$ But I'm not entirely sure of how to prove this. If anyone can think of a better function, please go ahead I would greatly appreciate it. Thanks in advance.
pneumatics
  • 133
2
votes
1 answer

How are these two terms asymptotically equal?

My teacher claim these two are the same in a proof, but I'm not sure if this is correct. Could anyone shed me some lights? $$\log_2((\lceil \log_2{n} \rceil)!) = \log_2(n) \cdot \log_2(\lceil \log_2(n) \rceil)$$ The original proof was $$O(\lceil…
IORI
  • 23
2
votes
1 answer

Does the big o notation always denotes the grow rate of the function?

According to Wikipedia, big O notation characterizes functoins according to their growth rates, but I have some confusion about it. For example, we say $f(x)=O(g(x))$ as $x\rightarrow a$ if and only if there exist positive numbers $\delta$ and $M$…
Searene
  • 981
1 2 3
…
74 75