# Questions tagged [asymptotics]

Questions involving asymptotic analysis, including growth of functions, Big-$O$ notation, Big-$\Omega$ and Big-$\Theta$ notations.

7,426 questions
Filter by
Sorted by
Tagged with
11 views

92 views

### What is the asymptotic expansion of $x_n$ where $x_{n+1} = x_n+1/x_n$?

Let $x_{n+1} = x_n+1/x_n, x_0 = a \gt 0$ and $y_n = x_n^2$. What is the asymptotic expansion of $x_n$ ($y_n$ will do)? I can show that $y_n =2n+\dfrac12 \ln(n) + O(1)$. Is there an explicit form for ...
48 views

### What is big O notation of the following functions?

So I have few simple functions I wrote and I would like to find out how to calculate their big O notation. This is my first function: ...
23 views

### How do I calculate Big Omega Notation for a function?

I was looking at the definition of Big Omega: \begin{align} \Omega(g(n)) &= \{ f(n): \text{ there exist positive constants }c \text{ and }n_0 \\ &\ \ \ \ \ \ \ \ \text{ such that }...
37 views

### How to neatly organize all real increasing functions?

Let $I$ be the set of increasing functions $\mathbb{R}\longrightarrow\mathbb{R}$ modulo asymptotic behavior, i.e. f\sim g \qquad\Longleftrightarrow\qquad \lim_{x\rightarrow+\infty}\...
25 views

### Behaviour of the Gamma function near zero

The Gamma function on the positive real half-line is defined via the reknown formula $$\Gamma(z)=\int_0^\infty x^{z-1}e^{-x}dx, \quad z>0.$$ A classical result is Stirling's formula, describing ...
67 views

### Asymptote for $y=\frac {x^2}{kx+1}$

We want to find the asymptote of $$y=\frac {x^2}{kx+1}$$ as $x\to \infty$. By synthetic division or binomial expansion, we arrive at $$y=\frac 1k \left(x-\frac 1k\right)$$ which is the correct answer. ...
35 views

21 views

21 views

33 views

### How to prove $\ln(n) = o\left(e^{\ln(n)^{1/3}}\right)$

I want to prove, that $\ln(n) = o\left(e^{\ln(n)^{1/3}}\right)$ ((Landau-Notation)) Normally I would do this by showing that $$\lim _{n \rightarrow \infty} \frac{\ln (n)}{e^{\sqrt[3]{\ln (n)}}}=0$$ ...
42 views

### How close is the sample mean $\mu_N$ for $N$ random variables to the sample mean $\mu_{N-1}$ for $N-1$ random variables?

Define $\mu_{N}$ to be the sample mean for $N$ i.i.d. random variables that each have mean $\mu$ and variance $\sigma^2$: $$\mu_{N} := \frac{1}{N} \sum_{i=1}^N X_i.$$ Now consider the sample mean if ...
27 views

### Very Hard : Error Bound on asymptotical approximation [duplicate]

Very Hard: Suppose I have a polynomial $g(x)=x^p$+ lower order terms. Asymptotically the inverse is $g^{-1}(x) \sim x^{1/p}$ for large $|x|.$ What is a bound of the error of this asymptotical ...
36 views

### Are these two asymptotic notations equal?

I see two notations and try to understand these are the same or not? (from two views) $O( n * (log m) * (log n))$ is equal to $O( n * (log m + log n))$ from logarithm property and from asymptotic ...
56 views

### Asymptotic formula for Mean of Sum of Power of Divisors $\frac{ \sum_{i=1}^{n}\sigma_v(i)}{n}\sim\frac{n^v\zeta(v+1)}{v+1}$

Question: Define the sum of $v$-powers of divisor $\sigma_v(n)=\sum_{d|n}d^v$ for $v \in \mathbb{R}$. Prove that for all $v>0$, $$\frac{ \sum_{i=1}^{n}\sigma_v(i)}{n}\sim\frac{n^v\zeta(v+1)}{v+1}$$ ...
Suppose $f(x) = x^p +$ lower order terms. Then Asymptotically $f^{-1}(x) \sim x^{\frac{1}{p}}$ for large $|x|$. How can we bound the error in this asymptotic approximation in terms of $|x|$
Let $f$ and $h_1$ be monotone functions. Let $g$ be the inverse function of $f$ and $h_2$ the inverse function of $h_1$. Furthermore we know that $f\sim h_1$. If the last statement holds - under what ...