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

Constant $c$ such that a certain function goes to $0$.

I am studying the function $${\sqrt x(\ln x)^{(-(\ln x)^{1/k})^5}\over xe^{-(\ln x)^{6/k}}}.$$ According to Desmos, this seems to go to $0$ for $k\ge 3$, but not for $k\le 2$. I was wondering if there was a simple explanation why, but I've found it…
marcelgoh
  • 1,794
0
votes
0 answers

Testing hypothesis about variance of non-normal population

Let $X_1,X_2,\cdots$ be i.i.d. from a distribution $F$ with mean $0$ and unknown variance $\sigma^2$ and having four moments. A common test for testing $H_0:\sigma^2=1$ vs $H_1:\sigma^2>1$ is to reject $H_0$ for large values of…
QED
  • 12,644
0
votes
2 answers

Asymptotics analysis of this expression

How to analyze the asymptotics of $\log(n-1)-\frac{1}{2}n^{\alpha+1}+\frac{1}{2}n\log(1+n^\alpha)$? $\alpha<0$, when $n$ goes to infinity. When does it goes to $-\infty$ when $n$ goes to $+\infty$? I have no experience of dealing with this type.…
happyle
  • 183
0
votes
2 answers

Showing $(\log n)^k = O(n)$, where $k\in\mathbb{N}$

I'm somewhat convinced by taking the limits of $\frac{n}{(\log{n})^k}$ (i.e. proving little $o$ to prove big $O$), but am struggling to prove that it is the case via the formal definition; say the following: We say that a function $f(n)$ is…
David
  • 1,510
0
votes
1 answer

Estimator of variance of an exponential distribution

I have a sample of $X_1,\ldots,X_n$ observations from an exponential distribution ($p(x)=\lambda \exp(-\lambda x)I(x>0)$. I'm struggling with how to prove that $(\bar{X})^2$ is an asymptotic normal estimator of $\lambda^{-2}$ and how to find the…
Evgenii G
  • 19
0
votes
0 answers

Asymptotic complexity with a parameter between 0 and 1

I have an algorithm with running time depending on a parameter $ x \in (0, 1) $. How is the asymptotic complexity of such algorithms typically analized? In my particular case the running time approaches ∞ as x -> 1 but I don't know what I can say…
martinkunev
  • 269
0
votes
0 answers

Prove sorting algorithm has $Ω$ complexity by considering max inversions?

I came across a question: Prove that any sorting algorithm that only compares and swaps contiguous values ​​has a cost (worst case) $Ω(n^2)$ The question tries to be based on the fact that we do $\frac{n \times (n-1)}{2}$ inversions in the worst…
Kim
  • 1
  • 1
0
votes
1 answer

Big O notation and Infinite series

Suppose I know $\displaystyle\sum_{n\leq x}f(n)=O(g(x))$. Can I deduce that $\displaystyle\sum_{n\geq x}f(n)=O(g(x))$? I think it should be true, and if anything, it should be a weak bound.
Shean
  • 877
0
votes
1 answer

Prove or disprove $f\left(n\right)=\Theta\left(g\left(n\right)\right)$

Definitions: $\mathbb{R}^{++}=\left\{ x\mid0
CStudent
  • 67
0
votes
1 answer

Asymptotic analysis of a given function

In a certain text, it was given that a function is given by $$\varphi_{n}(t)= \sqrt{\frac{(\eta)_n}{n !}} \tanh^{n} (\alpha t) \operatorname{sech}^{\eta}(\alpha t)$$ where $\eta$ and $\alpha$ are some constant number, $t$ is time. Further, it was…
Erosannin
  • 31
0
votes
0 answers

Prove that $2^n=\omega(n)$

Is this a valid proof? Definition: $f\left(n\right)=\omega\left(g\left(n\right)\right)$ if $\underset{n\rightarrow\infty}{\lim}\frac{f\left(n\right)}{g\left(n\right)}=\infty$ for $f\left(n\right),g\left(n\right):\mathbb N\rightarrow\mathbb…
CStudent
  • 67
0
votes
0 answers

The implications of: $\sum ^\infty _{k=1} \frac{a_k}{n^k}=O(\frac 1 n)$

I am reading this note on the Jackknife estimator, and I'm confused about this part: Suppose $$ \sum ^\infty _{k=1} \frac{a_k}{n^k}=O(\frac 1 n), $$ then $$ \sum ^\infty _{k=1} a_k (\frac 1 {n^{k-1}}-\frac{1}{(n-1)^{k-1}}) = \frac{a_2}{n^2} +…
WinnieXi
  • 91
0
votes
1 answer

Asymptotic notation for $O(1)/\mathsf{poly}(n)$

Consider $n \in \mathbb{N}$, a constant $s \in O(1)$ and a polynomial value $Q \in \mathsf{poly}(n)$. How can $\frac{s}{Q}$ be written asymptotically? We have $\frac{O(1)}{Q}$, is this value just $o(1)$ for sufficiently large $Q$? If yes, why…
pandora
  • 178
0
votes
2 answers

What is the meaning of $g(n) = 2^{O(f(n))}$?

Given functions f and g, as above, what exactly does it mean? Does it mean, for example, that g(n) is exactly equal to $2^{h(n)}$ for some function h contained in $O(f(n))$ - or does it rather mean that $g(n) = O(2^{h(n)})$ for some function h…
Abhishek Manikandan
  • 77
0
votes
1 answer

Formula for a graph that has an asymptote at $y = 1$ where $0\le y<1$ and $0\le x<\infty$

Is it possible to have a formula that describes the following: $0\le y<1$ and $0\le x<\infty$ There is an asymptote at $y = 1$; so as $x$ approaches $\infty$, $y$ approaches $1$. I have played with all manner of $y=1/x^n$ and $x=1/y^n$, square root…
Bryon
  • 227
1 2 3
…
74 75