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

analyse and computations on asymtotics are contradicting

Let $$E:=\overbrace{-2C_0-(n-2)C_1}^A+(4+(n-2)\overbrace{(2C_1+C_2)}^B)\cdot p-(n-2)\overbrace{(C_1+C_2-C_3)}^Cp^2\\$$ I got a question when I tried to give asymptotics analysis of $E^2$. It looks contradiction to the computation obtained in…
chloe
  • 512
2
votes
1 answer

How to write this in big O notation?

I have a function $f(m,n)$ for which there exists a constant $\alpha<2$ such that, for fixed $m$, as $n\rightarrow\infty$, we have $f(m,n)\leq\alpha\sqrt{m/n}$, and for fixed $n$, as $m\rightarrow\infty$, we also have $f(m,n)\leq\alpha\sqrt{m/n}$. …
Lyly Truong
  • 23
  • 2
2
votes
2 answers

Condition on the inequality holds asymptotically

$$(n-1) \left[\frac{1}{2}\log\left(\frac{1}{2p}\right)+\frac{1}{2}\log\left(\frac{1}{2(1-p)}\right)\right]>2\log(n)$$ where $p$ is a function of $n$. How to find out on which condition of $p$ such that the inequality holds (asymptotically)? From the…
M.K
  • 541
2
votes
1 answer

Law of iterated logarithm and big O notation

I have read the statement of Law of iterated logarithm is like for some random variable $Y_i$ $$\lim\sup_{n\rightarrow\infty}\frac{\sum_{i=1}^nY_i}{\sqrt{2\log\log n}}=1\ a.s.$$ But I have also found another version using big O notation…
toki
  • 95
2
votes
0 answers

Convergence to non-degenerate limit.

If $X_1,X_2......$ follow Poisson$(λ)$. Can we find suitable constants $a_n$ and $b_n$ such that $a_n(Y_n - b_n)$ converges to a non degenerate limit where $Y_n = (1 - \frac{1}{n})^{n\bar{X}_n}$. I have shown that $Y_n\rightarrow e^{-\lambda}$…
user87455
  • 81
2
votes
2 answers

How to show that a "Big-Oh" set is a subset of another?

Let's say we have two "Big-Oh" sets called $\text{Constant}$ and $\text{Logarithmic}$, such that one has $O(1)$, and the other has $O\big(\log(n)\big)$, respectively, how would I show that $\text{Constant} \subseteq \text{Logarithmic}$?
Sal Rahman
  • 244
2
votes
2 answers

Show that $f \in \Theta(g)$, where $f(n) = n$ and $g(n) = n + 1/n$

I am a total beginner with the big theta notation. I need find a way to show that $f \in \Theta(g)$, where $f(n) = n$, $g(n) = n + 1/n$, and that $f, g : Z^+ \rightarrow R$. What confuses me with this problem is that I thought that "$g$" is always…
Sal Rahman
  • 244
2
votes
0 answers

Compare $n!$ and $(\log n)^n$

I think that $n!$ grows fast than $(\log n)^n$ but how do you show that? I'm doing a practice exam right now and I have to compare functions. Is this correct? $28 <\log n^{2020} < 5n^{3/7} < 2^{n^{1/2}} < (\log n)^{n/2} < n! < n^n$ I know how to…
Lena67
  • 209
2
votes
1 answer

Basic Big-O Question

I had 2 very small queries regarding Big-O notation: If $f(x) = O(g(x))$, then for any constant a, is it the case that $a^{f(x)} = O(a^{g(x)})$? If $f(x) = O(g(x))$ and $h(x) = O(i(x))$, then does $h(x)^{f(x)} = O(i(x)^{g(x)})$? Any help would…
Abhishek Manikandan
  • 77
2
votes
2 answers

How do I show that one function isn't growing slower or equal than the other

I had a lecture on BigO notation, and I received a problem set to solve, but unfortunately we always get harder examples to solve that those presented(those which are presented are always some basic cases) during the lecture. Here is the actual…
viGor
  • 21
2
votes
0 answers

growth rate of function versus its derivative

Suppose a positive and strictly monotone increasing differentiable function $f: \mathbb R \rightarrow \mathbb R $ is $O(g(x))$ for some function $g$ that is strictly positive for large $x$, and suppose $g$ is $O(x)$ (i.e. linear growth or slower).…
Jong
  • 236
2
votes
0 answers

Property of little $o$-notation $o(f(x)) + o(g(x)) = o(f(x) + g(x))$

Apostol' Calculus gives $o$-notation as follows: Assume $g(x) \neq 0$ for all $x \neq a$ in some interval containing $a$. The notation $$ f(x) = o(g(x)) \quad \text{as}\ x\to a $$ means that $$\lim_{x\to a}\frac{f(x)}{g(x)} = 0.$$ how to prove…
yanpengl
  • 143
2
votes
0 answers

Aymptotic analysis for Following fucntions

Below is an excercise from algorithm design manual For each pair of expressions (A,B) below, indicate whether A is O, o, Ω, ω, or Θ of B. Note that zero, one or more of these relations may hold for a given pair; list all correct ones. A ------- …
gopal
  • 271
  • 2
  • 9
2
votes
1 answer

Asymptotic analysis comparision for $2^n$ and $(3/2)^n$

1) $$f(n) = 2^n\,,\quad g(n) = (3/2) ^ n$$ Is $f(n) = \Theta(g(n))$? Can someone please explain this to me ? 2)$$f(n) = n^2+\log n\,,\quad g(n) = n^2$$ I know that $f(n) = \Theta(g(n))$ but how can I get the constant $c$ to prove the…
gopal
  • 271
  • 2
  • 9
2
votes
1 answer

Asymptotic relation between $n^{1/3}$ and $(\log n)!$

What is the asymptotic relation between $n^{1/3}$ and $(\log n)!$? I compared the graphs and of course, $\mathcal{O}(n^{1/3})=(\log n)!$. However, for a more concrete proof, I compared the $\log$ of both functions although, I am not sure if this is…
reyna
  • 2,101
1 2 3
…
74 75