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
3
votes
3 answers

How to prove that $O(n) \cdot O(n^2) = O(n^3)$?

Would the solution be something like let $fn \in O(n)$ so $ fn \le c1 \cdot n$ and $ gn \in O(n^2) $ so $ gn \le c2 \cdot n^2$ where $c1,c2$ constants so $ fn*gn \le C \cdot n^3$ so $ fn*gn \in O(n^3)$ so $O(n) \cdot O(n^2) = O(n^3)$
Leon Vitanos
  • 131
3
votes
0 answers

Big O-Notation and lim sup

this may sound like a stupid question, so please excuse me for that. From my understanding after quickly reading up on it (only know the definition of general limits before), $\limsup\limits_{x\rightarrow\infty} sin(x) = 1$. Because $f \in O(g)…
Maxbit
  • 145
3
votes
1 answer

Questions about Big-O notation

I understand the formal definition of Big-O: $f(n)$ is $O(g(n))$ if there exist constants $N$ and $c$ such that for $n>N$ we have that $f(n) \leq c\cdot g(n)$. However, the problem is that, by this definition, $2n+1$ is $O(n^2)$ even though it is…
Hossmeister
  • 817
3
votes
1 answer

Which one is asymptotically larger? $100n+\log n$ Or $n+(\log n)^2$

In the book Algorithms by Sanjoy Dasgupta in 1st chapter exercise Q.1. In each of the following situation, indicate whether $f = \mathcal{O}(g)$ , or $f = \Omega(g) $, or both (in which case $ f = \Theta(g) $ (c) $f(n) = 100 n + \log\,n $ , $g(n) =…
Brij Raj Kishore
  • 339
3
votes
1 answer

Is there $\epsilon>0$ such that $n\log n=\Omega (n^{1+\epsilon})$

It is obvious that $n\log n=\omega (n)$. But does this necessarily mean that $\exists \epsilon>0$ such that $n\log n=\Omega (n^{1+\epsilon})$? My intuition says yes, but I'm not sure what $\epsilon$ should be.
H.Rappeport
  • 1,536
3
votes
1 answer

Question about the asymptotic growth rate of two functions

If we have arbitrary constants $x > 1$ and $y > 0$, how can I go about proving that $x^n$ is not $O(n^y)$? I think this may be achievable using recurrences but I am not sure about the methodology behind that, so any help is appreciated.
Harrison W.
  • 777
3
votes
1 answer

Stationary Phase, approximate the leading behavior of the integral and determine the dependence on n.

The given integral is: $$\int_{-\pi/2}^{\pi/2}\cos(nt-\lambda\cos t) dt, \lambda \rightarrow \infty $$ This can be rewritten as a complex exponential so it's $$ Re \left[ \int_{-\pi/2}^{\pi/2}\ e^{i(nt-\lambda\cos t)} dt \right] \lambda \rightarrow…
Jade
  • 159
3
votes
1 answer

Is this cheat sheet over big-$O$ and related notations accurate?

When familiarizing myself with big-$O$ and similar notations, I found this cheat sheet (which I took the liberty of transcribing): $$\begin{array}{c|c} \text{big-$O$ notation} & \text{limit definition} \\[2ex] \hline f\in o(g) &…
gen-ℤ ready to perish
  • 6,610
3
votes
1 answer

What does f(n) and g(n) mean in this question?

The question I’m trying to answer is about asymptotic inequality. The question states, If $f(x)$ and $g(x)$ are polynomials with respective leading terms $ax^{n}$ and $bx^{m}$ then $\frac{f(n)}{g(n)} \sim \frac{a}{b}x^{n-m}$. I am confused what…
user511607
  • 93
3
votes
1 answer

Curious case of asymptotic equivalence

Let us consider $n$ a positive integer and $F(n)$ an increasing function of $n$. What conditions $F$ should fulfil to obtain the following: $$\lim_{n \to \infty} \frac{F(n)}{F(n-1)} = 1$$ ? It appears that this is wrong if $F(n)=exp(n)$. Are there…
Dingo13
  • 435
3
votes
1 answer

Asymptotic equivalence and composition

I have not found the complete list of operations that we can perform on asymptotic equivalences using the $\sim$ notation. This equivalence is defined as follows: $f \sim g$ if $\lim_{x \to \infty} f(x)/g(x) = 1$. What about the composition? Let us…
Dingo13
  • 435
3
votes
1 answer

Big O and product

First of all give the definition of $O(n)$ and use it to demonstrate that: $O(n) * O(n) = O(n^2)$ I know that this is true because: $O(f(x))*O(g(x)) = O(f(x)g(x))$ but I don't know how to demonstrate it, even with the definition: $$f(x) = O(g(x))$$…
Christian Giupponi
  • 687
3
votes
3 answers

Time complexity of writing a number as power of 2's

I'm wondering about the time complexity of writing a number as power of 2's. For example writing $n=218$ as $2 + 2^3 + 2^4 + 2^6 + 2^7$. It seems to me that we do $\lceil log_2^n \rceil $ divisions. Each division costs $O(n^2)$ so an upper bound is…
SpiderRico
  • 483
3
votes
2 answers

Big - O Problem

Show that $a^n$ = O(n!) where a>0 I can see how it is true but I don't know how to work out the values for C and K in $|f (x)| ≤ C|g(x)|$ whenever $x > k.$ I have been looking at this for ages so any help would be great.
John Jo
  • 31
3
votes
1 answer

Can I disprove the following statement with this example?

I do not know much about O notation so could you please help me, I have to prove or disprove the following statment: $\forall f,g: \mathbb{N} \rightarrow \mathbb{R}_{\geq 0} \text{ }f=O(g) \text{ or } f=\Omega(g)$ Can I disprove this statement with…
nakajuice
  • 2,549
1 2 3
…
74 75