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

Is $n4^n$ greater or within the realm of $\theta{\left(4^n\right)}$

Basically a Big O question. Is $n4^n$ or any other exponential function greater than $4^n$ in terms of Big O notation or not?
user65271
  • 3
0
votes
1 answer

Which Function is Big-O of the Other

Given $f(n)=nlog(n)$ and $g(n)=10^{-6}n^2$, I am asked to find whether $f\in O(g)$ or $g \in O(f)$. The book claims that $f \in O(g)$, but I do not see how that is true. If it is true, there exists a number $C$ such that $$nlog(n) <…
J. Dunivin
  • 3,103
0
votes
1 answer

Proving the asymptotic relationship between $(lg\cdot n)^{0.5}$ and $lg\cdot (n^{0.5})$?

Say $f(n) = (lg\cdot n)^{0.5}$ and $g(n) = lg\cdot (n^{0.5})$ It would appear that $f(n) = O(g(n))$ for $n \gt 55$ correct? How do I go about proving the the relationship for this?
Badger
  • 229
0
votes
1 answer

How to prove that $\left(\log \log n\right) \times \left(\log \log \log n\right) = Ω\left(\log n\right)$

Is $$\log \log n \times \log \log \log n = \Omega(\log n) $$ How can we prove it. Actually I'm trying to prove that $f(n) = \lceil(\log \log n)\rceil !$ is polynomially bounded. It means $$c_1 n^{k_1} \leq f(n) \leq c_2 n^{k_2} \quad \forall n >…
Atinesh
  • 1,239
0
votes
1 answer

Proving the asymptotic relationship between two functions

I was playing around with numbers a few days ago and found an asymptotic approximation to two functions: $$y=-\ln{x}$$ And $$y=x^{1-\frac{1}{x}}-x$$ Can I have a proof that it is (or isn't) asymptotic? (I'm pretty sure it is but I'm not 100% sure)
user253055
0
votes
0 answers

Asymptotic equality

Why do we have this: For $x = o(1)$, $1 - x = \exp(-x-O(x^2))$? I know the idea is from the Taylor's formula, but it sounds weird to me. I would like to know a clear explanation for it? To be more clear, I know that these two things are…
user24175
  • 199
0
votes
3 answers

Is there a simpler proof that $n^2 = O(2^n)$?

I am wondering if there is a simpler proof that $n^2 = O(2^n)$ which doesn't involve several layers of induction. My proof is as follows (sorry for the bad formatting). Proof: $n^2 = O(2^n)$ We will show that $\exists k,c \in \Bbb R_{>0} : \forall…
iamasupern0va
  • 3
  • 1
0
votes
3 answers

Is this proof for big-Oh of $(x+2)log(x^9 + 5)$ correct?

Is my proof that $(x+2)log_{2}(x^9+5)$ is $\mathcal{O}(xlog_{2}x)$ correct when x tends towards infinity? $\left | f(x) \right | = \left | (x+2)log_{2}(x^9 + 5) \right |$ $\leq \left |(x+2)log_{2}(x^{10}) \right |$ for $x \geq 2$ <---- This is the…
Julia
  • 496
0
votes
1 answer

Slant asymptote of a function in x and y

After looking for the asymptotes of the function: $y^3+2y^2-x^2*y+y-x+4=0$ I found the answers y=0, y=-x-1 and y=x+1. This is almost exact: the last one should actually be y=x-1. To find the result, I substituted x=my+c in the equation, which…
benox
  • 11
0
votes
1 answer

Asymptotes and their like

Can an asymptote be a curve? From what I have read, it suggest that the numerator must strictly be only one degree higher than than the denominator. However mathematically speaking, a equation like $f(x) = \frac{x^3(x-1) + 1}{x-1}= x^3 +…
WhosSu
  • 45
0
votes
1 answer

Big-Oh of $(\log_bn)^c$ is $O(n^d)$

I'm a CS freshman. In my discrete math textbook, it says ... whenever b > 1 and c and d are positive, we have $(\log_bn)^c$ is $O(n^d)$, but $n^d$ is not $O((\log_bn)^c)$ But why? Using Wolframalpha I see the plot show for b=2,c=3,d=1, it the…
RexYuan
  • 140
0
votes
1 answer

Prove that $2^{n+1} = \Theta(2^n)$?

I need to prove that $2^{n+1} = \Theta(2^n)$? To do this, I need to show that there are positive constants $c_1,c_2$ such that $$c_1 2^n \le 2^{n + 1} \le c_2 2^n$$ ...for all sufficiently large $n$. To find $c_2$, I know that I just need to find…
User
  • 907
0
votes
1 answer

Disprove $f(n) = 2^{2n}$ is $O(2^n)$

Disprove $f(n) = 2^{2n}$ is $O(2^n)$ Informally I know that this means we have to show that $2^{2n}$ grows much faster than $2^n$. More formally, I know that we need to show that for any $N$, there is a constant $c>0$, so that for all $n>N$ such…
User
  • 907
0
votes
3 answers

Prove or disprove $f(n)$=$2^{n+1}$ is $O(2^n)$

I need to prove or disprove $f(n)$=$2^{n+1}$ is $O(2^n)$. I believe this statement is true, so I want to prove it. I know that $f(n)$ is $O(g(n))$ if there are positive constants $C$ and $k$ such that $f(n) \leq C g(n)$ whenever $n > k$. Here is…
User
  • 907
0
votes
0 answers

Finding the asymptotic expansion of $\sin(3x)$ using asymptotic sequence $\{\ln(1+x^n)\}_n$

Finding the asymptotic expansion of $\sin(3x)$ using asymptotic sequence $\{\ln(1+x^n)\}_n$. In the notes and lectures the only example that was given was an expansion for $\tan(x)$ where she literally just swapped the $x$ terms for $sin x$ terms…
Daniel Piggott
  • 75
1 2 3
…
74 75