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

Two Big O questions

Can a function belong to two different big Os if the latter is bigger? for example: $n \in O(n) $ and $n \in O(n^2)$ for $O(n^2) \ge O(n)$ I guess this is not always true, but for the above case it would work as by definition we can have $n=C=1 or…
glockm15
  • 587
2
votes
0 answers

Little o Notation: Prove that the statement is false

Prove false: $\cot x=o(x^{-1})$ as $x\to 0$ Note: $x_n=o(\alpha_n)$ means $\lim\limits_{n\to\infty}\frac{x_n}{\alpha_n}=0$. Or, for some $\epsilon_n\geq 0$, we have $\epsilon_n\to0$ and $|x_n|\leq\epsilon_n|\alpha_n|$ My attempt: By definition, this…
Thomas
  • 329
2
votes
1 answer

Show $\sum\limits_1 ^x \frac{f(n)}{g(n)} \sim x $

Assume $f(n)$ is defined over the positive integers with $$\sum_{1}^x f(n) \sim xg(x),$$ where $g$ is a differentiable function with $xg'(x) = o(g(x))$. I am having trouble showing that $$\sum_1 ^x \frac{f(n)}{g(n)} \sim x .$$ This doesn't seem…
Dominated Convergence Theorem
  • 923
2
votes
3 answers

How to find asymptotes of $y=ax+b+\frac{c+\sin x}{x}$

How can we find the asymptotes of $y=ax+b+\frac{c+\sin x}{x}$?
liesel
  • 869
2
votes
2 answers

How to show $n! = \omega\big((\frac{n}{3})^{n+e}\big)$?

I'm learning some mathematics by myself and get stuck. The problem is to show that $n! = \omega\big((\frac{n}{3})^{n+e}\big)$, $\omega$ is the asymptotic notation. It's from the Problem Set 7 of MIT 6.042
xwb1989
  • 305
  • 1
  • 2
  • 6
2
votes
1 answer

Some asymptotics with log

I would like to answer the question whether $$ (1+\frac{\log x}{x})^x\cdot\frac{\log x}{x}-1\sim \log x-1\text{ as }x\to\infty. $$ I think this boils down to the question whether $$ (1+\frac{\log x}{x})^x\sim x\text{ as }x\to\infty. $$ I think this…
Rhjg
  • 2,029
2
votes
2 answers

Approximate $\prod_{k=1}^nk^\binom{n}{k}$

I'm looking for an asymptotic approximation of $\prod_{k=1}^nk^\binom{n}{k}$ in order to get a better impression of its growth rate. Does anyone know how to deal with the given product? Any hints are appreciated.
MaxWell
  • 319
2
votes
3 answers

Is -2n a big Oh of n as n goes to infinity?

Based on the definition of the upper asymptotic bound, we have that : $$|n| < K |-2n| $$ for $ K = 1$ for example and as $ n $ goes to $+\infty$, so the definition would lead us to say that $-2n$ is an asymptotic upper bound of $n$; Which doesn't…
IliassA
  • 57
2
votes
0 answers

What is the Big-$\Omega$ of $\prod_{i=2}^n \log{(i)}$

It's similar to this question, but I'm looking for the lower limit.
ChaosPredictor
  • 303
  • 3
  • 12
2
votes
2 answers

Big-O: If $2^{f(n)}=O(2^{g(n)})$, prove $f(n)=O(g(n))$

It's similar to this question but upside down. Suppose that both $f(n)$ and $g(n)$ are nonnegative functions. If $2^{f(n)}=O(2^{(g(n)})$, is $f(n)=O(g(n))$ true too? If not, give a counterexample.
ChaosPredictor
  • 303
  • 3
  • 12
2
votes
0 answers

Are my calculations concerning the growth rate of $f(n) = \sum_{k=0}^n \min(2^k, 2^{2^{n-k}})$ correct?

Having $$f(n) = \sum_{k=0}^n g_n(k), \; g_n(x) = \min(2^x, 2^{2^{n-x}})$$ I want to know whether $\mathcal O(f(n)) \subsetneq \mathcal O(2^n)$. Since $g_n(x) \le 2^x$ it is at least $f(n) \in \mathcal O(2^{n+1}-1) = \mathcal O(2^n)$. Let $x_n$ be…
Simon S
  • 234
  • 1
  • 9
2
votes
1 answer

Does $\omega(1)$ mean non-constant?

Let's say I have a discrete structure of size $n$, and some characteristic $a$ of that structure for which it holds that $a= \omega(1)$. Is this equivalent to say that $a$ can not be a constant but it has some dependence on $n$?
jack
  • 23
  • 2
2
votes
1 answer

How to prove asymptotic property with big O notation?

Could you help me to show: $g(x,\epsilon)+f(x,\epsilon)=O(|\phi(x,\epsilon)|+|\psi(x,\epsilon)|)$ but $g(x,\epsilon)+f(x,\epsilon)\neq O(\phi(x,\epsilon)+\psi(x,\epsilon))$ (both when $\epsilon\to0$), where $O$ stands for the big Oh notation?
Lindsay
  • 21
2
votes
1 answer

Show $n! \in O(n^n)$ but $n^n \notin O(n!). $

I'm not entirely sure if this proof would suffice, but here's what I have, $$\text{Show }n! \in O(n^n) \text{ but } n^n \notin O(n!).$$ Consider, $ c \geq\frac{|f(n)|}{g(n)}$ by Big O definition. Let $f(n) = n!$ and $g(n) = n^n…
Philip
  • 198
2
votes
1 answer

O-Notation: $O(f) = \bigcup_{g \in O(f)} O(g)$

I am stuck with this problem. $$O(f) = \bigcup_{g \in O(f)} O(g)$$ I have tried to prove it with the assumption that $g \in O(f) \rightarrow f \in O(f)$, which I already have proved, but I am not sure how to continue. Has someone maybe an…
MWP
  • 21
1 2 3
…
74 75