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

learn more… | top users | synonyms (1)

0
votes
1answer
76 views

How can I solve this recurrence problem?

Given a function $$ f(n) = f(5n/13) + f(12n/13) + n \;\;\;\;∀n \geq 0 $$ I would like to find a function $g(n)$ such that $f ∈ Ө(g(n))$.
2
votes
1answer
17 views

Show that $\log^{i} n \in O(n^{j})$ for $i,j > 0 $

I want to show that $$\log^{i} n \in O(n^{j})$$ I tried to apply L'Hospital and came up with the following: $$\lim\limits_{n \rightarrow \infty}{\frac{\log^{i} n}{n^{j}}} =$$ $$\lim\limits_{n ...
1
vote
1answer
48 views

What are conditions under which convergence in quadratic mean implies convergence in almost sure sense?

What are the conditions on the sequence on $\{X_n\}$ (apart from the degenerate random variable), under which it can be claim that $||X_n-X||_{L^2(\mathbb{R})}\rightarrow 0$ implies $X_n\rightarrow ...
0
votes
1answer
21 views

Asymptotic behaviour of Hilbert transform

Let $f$ be a bounded function on $\mathbb{R}$ with compact support include in $[-K,K]$. Show that $$ H(f)(x)=\frac{a}{\pi x}+O(\frac{1}{x^2})$$ where $a=\int f(t)dt$ and $H$ denote the Hilbert ...
4
votes
2answers
168 views

Show that if $\int_0^x f(y)dy \sim Ax^\alpha$ then $f(x)\sim \alpha Ax^{\alpha -1}$

Let $f$ be a real, continuous function defined on $[0,\infty)$ such that $xf(x)$ is increasing for all sufficiently large values of $x$. Show that if $$\int_0^x f(y)\,dy \sim Ax^\alpha \quad ...
0
votes
0answers
18 views

Estimating the derivative of the difference function from that of a function

Suppose that $f$ is a twice differentiable function in an interval $(N,2N)$. We write $f_1(n,h)=f(n+h)-f(n)$, i.e., $f_1$ is the difference function. Then, a proof I'm reading estimates that if ...
2
votes
0answers
31 views

An advection problem with weak diffusion in asymptotic analysis.

Consider the following advection problem with weak diffusion: $$ \varepsilon\partial_{x}^2 u=\partial_{t}u+\partial_{x}u, $$ for $−\infty < x < \infty$, and $t > 0$ where $u(x, 0) = ...
0
votes
2answers
19 views

exponential boundedness of components given exponential boundedness of the norm

Let $v:[0,\infty)\rightarrow \mathbb{R}^n$ be a function such that $\forall t\ge 0$, $v_i(t)\ge 0$ and $$ ||v(t)||\le \beta ||v(0)||e^{-at}, t\ge 0$$ with $\beta,a>0$ can I conclude that for all ...
1
vote
3answers
30 views

Is this proof for big-Oh of $(x+2)log(x^9 + 5)$ correct?

Is my proof that $(x+2)log_{2}(x^9+5)$ is $\mathcal{O}(xlog_{2}x)$ correct when x tends towards infinity? $\left | f(x) \right | = \left | (x+2)log_{2}(x^9 + 5) \right |$ $\leq \left ...
3
votes
1answer
73 views

Asymptotic behaviour of $\int_0^1 g(x)\exp(-nx)dx$ as $n\rightarrow\infty$

Let $g:(0,1]\rightarrow\mathbb{R}_+$ be an invertible monotonically non-increasing function that integrates to $1$ and has $g(1)=0$, $g(0)=\infty$; eg. $g(x)=x^{-1/2}-1$ or $g(x)=\ln(1/x)$. I believe ...
2
votes
1answer
48 views

Big-O vs. Best Big-O

Is there a difference between the method to find a big-O function and the method to find the best big-O function. Take for example the following function: $f(n) = 1 + 2 + 3 + ... + n$ It is easy to ...
3
votes
1answer
77 views

Steepest descent method with movable maximum

Suppose we want to find the asymptotic behavior as $n \rightarrow \infty$ of the integral $$\int_C \frac{dz}{z} \frac{e^z}{z^n}=\int_C \frac{dz}{z} \exp(z-n \ln z)$$ where $C$ is some contour in the ...
0
votes
1answer
24 views

Why is this true - easy question concerning asymptotics of exponential

Suppose $\lambda > 0$ is constant as $t \searrow 0$. In my lecture notes it is written that $\left(1+\sum_{k=1}^{\infty} \frac{(-\lambda t)^k}{k!}\right) \lambda t = \lambda t + o(t)$ and ...
1
vote
2answers
61 views

Find whether $f(n) = o(g(n))$ or $g(n) = o(f(n))$

Find whether $f(x) = O(g(n))$ or $g(n) = O(f(x))$ where $$ f(n) = (\log n)^{\log n} \quad\quad\text{and}\quad\quad g(n) = 2^{(\log_2n)^2} $$ I found that $f(n) = n^{ \log {\log n}}$, ...
1
vote
0answers
26 views

Second order perturbed equation

I've been studying asymptotic behavior on Ordinary Differential Equations. While doing some excercises I found out one excercise which has had me thinking for a while, so I am asking humbly for your ...
3
votes
1answer
68 views

Reference for asymptotics on sum

Quite simply I'm looking for the large $m$ asymptotic behavior of \begin{equation} \sum_{k=1}^{m}{m\choose k}\frac{a^k}{k} \end{equation} where $a$ is a constant. This looks easy for someone who knows ...
0
votes
2answers
79 views

Summing divergent asymptotic series [closed]

I found the sine integral si to be $$Si (x)\sim \frac \pi 2+\sum _{n=1}^\infty (-1)^n \left(\frac{(2 n-1)! \sin (x)}{x^{2 n}}+\frac{(2 n-2)! \cos (x)}{x^{2 n-1}}\right)$$ Say I want to find ...
0
votes
1answer
22 views

Estimating size of partial euler product

What estimates are there for product over primes $p \leq x$ $\prod_{p \leq x}(1-\frac{1}{p^{r}})$ given $r$ is positive integer. Something better than $\prod_{p \leq x}(1-\frac{1}{p^{r}}) \leq ...
5
votes
1answer
647 views

Order of growth of the entire function $\sin(\sqrt{z})/\sqrt{z}$

Show that $$f(z)=\frac{\sin\sqrt z}{\sqrt z}$$ is an entire function of finite order $\rho$ and determine $\rho$. I observed that the two determinations of the square root differ only for the signum. ...
0
votes
1answer
21 views

Calculate the asymptotic growth of a sum that contains log or binom

I'm looking for a basic explanation how to calculate the asymptotic growth of sums. Take for example this one: $\sum_{i=1}^{lg(n!)} 2^{n^2}$ or this one: $\sum_{i=0}^{n} {n\choose{i}}$ The ...
1
vote
1answer
54 views

Is $\sqrt{2/(27\pi n)}\sim n^{-1/2}$?

Is $\sqrt{2/(27\pi n)}\sim n^{-1/2}$? Since $$ \sqrt{\frac{2}{27\pi n}}=\sqrt{\frac{2}{27\pi}}\cdot\frac{1}{\sqrt{n}}\sim\frac{1}{\sqrt{n}}=n^{-1/2}, $$ I would say, yes, of course.
1
vote
1answer
31 views

Prove/disprove the following asymptotic bound

Indicating with $p$ and $q$ prime numbers, is it true that for $x\rightarrow\infty$ $$ \sum_{\substack{p\leq x \\ p\equiv 1 ...
2
votes
1answer
28 views

Convergence to a distribution implies convergence of a logarithm?

Let $X_n$ be a sequence of almost surely positive real-valued random variables s.t. $$\sqrt{n} \, \left( X_n -a \right) \to_D \mathcal{N} ( 0, 1)$$ where $\to_D$ denotes convergence in distribution ...
1
vote
0answers
15 views

Stationary Phase method with Singular test function

Consider the following integral $I(x,t) = \int_{-\infty}^{\infty}\{F(k)exp(it\psi(k)) \}dk$ with $\psi(k) = (k-k_0)(\frac{x}{t}) - (\beta(k)-\beta_0)$ where $\beta_0=\beta(k_0)$ and $F(k)= ...
8
votes
0answers
116 views

Heat equation asymptotic behaviour 2

Let $D$ be the domain defined as $D := \{ (x,t): t \in [0,1) , \; x < (1-t)^\alpha \}$. Let $u(x,t)$ satisfy the heat equation $u_t = \frac{1}{2}u_{xx}$ in $D$, with initial condition: ...
0
votes
1answer
37 views

Asymptotic value of a Cauchy Singular integral

Let, $\zeta(x,t) = A_0sin(k_0x)cos(\omega t) + \frac{2k_0A_0}{\pi} \{\int_{0}^{\infty}\frac{cos(kx)cos(\beta t)-cos(k_0x)cos(\omega t)}{k^2-k_0^2}dk\}$ Here $\beta ^2 = gktanh(kh)\ and\ \omega^2 = ...
1
vote
1answer
59 views

Estimation of a probability of marginal values of a random variable

My question is related with this question on combinatorics of 0-1-matrices from MO. Trying to obtain a (asymptotic) lower bound for $\alpha(n)$ by probabilistic approach (see, for instance, “The ...
1
vote
0answers
21 views

Stationary Phase method with Singular test function

I'm stuck at the following integral $I(x,t) = \int_{-\infty}^{\infty}\{F(k)exp(it\psi(k)) \}dk$ with $\psi(k) = (k-k_0)(\frac{x}{t}) - (\beta(k)-\beta_0)$ where $\beta_0=\beta(k_0)$ and $F(k)= ...
4
votes
0answers
35 views

Asymptotic behavior of many derivatives

To compute the residue of a pole of very high order $M$ at $z=0$, one needs to compute $\frac{d^M}{dz^M} g(z)$ Suppose that $g(z)$ is a reasonable but not trivial function, that itself may depend on ...
0
votes
0answers
6 views

Multiscale expansion: Higher harmonics for Higher order solution

The following is related to he topic of "Evolution Equations for Slowly Modulated Weakly Nonlinear Water Waves Over Horizontal Sea Bed" from Sec 13.2, Theory and Applications of Ocean Surface Waves, ...
2
votes
3answers
104 views

The asymptotic behavior of an integral

The integral in hand is $$ I(n) = \frac{1}{\pi}\int_{-1}^{1} \frac{(1+2x)^{2n}}{\sqrt{1-x^2}}\, dx $$ I dont know whether it has closed-form or not, but currently I only want to know its asymptotic ...
1
vote
1answer
38 views

How to solve this type of exercises $\sqrt{x^6+x^5-2x^3+O(x^2)}$

I have a simulation test with this type of exercise, asymptotic expansion: $$\sqrt{x^6+x^5-2x^3+O(x^2)}$$ with $$ x\rightarrow \infty$$ I have studied the theory of Landau's symbols but I have no ...
1
vote
2answers
84 views

When does $f\sim g$ implies $f'\sim g'$?

Given two $C^1$ functions $f,g:[0,+\infty)\to [0,+\infty)$ such that $f(x)\sim g(x)$ as $x\to\infty$, which good conditions guarantee that $f'(x)\sim g'(x)$? I thought that monotonicity of the ...
1
vote
0answers
38 views

Can we find the closed-form of the series?

I want to calculate the series $$ F(N,g)=\frac{1}{g^N}\sum_{m=0}^{N(g-1)}\Big(\sum_{i=0}^{[m/g]}(-1)^i\binom{N}{i}\binom{N-1+m-gi}{N-1}\Big)^2 $$ where $g=2,3,4,\cdots$, and $N$ is any positive ...
1
vote
1answer
286 views

Limit involving tetration

Let the notation be $a^{\wedge\wedge}b = \underbrace{a^{a^{\cdot^{\cdot^{a}}}}}_{b\,times}$ for tetration. My mentor conjectured the following: Let $n$ be a positive integer, then let $A(n)$ be ...
4
votes
0answers
134 views

Heat equation, boundary gradient singularity

Consider the Cauchy-Dirichlet problem for the heat equation in a non-cylindrical region $\Omega \subset \mathbf{R}^+ \times \mathbf{R}$: $\Omega = \{ (t,x): \; 0 \leq t \leq 1, \; x \leq ...
4
votes
3answers
161 views

What is $\lim_{x\to 0} \sum_{n=2}^\infty \frac{\sqrt{x}\ln n}{1+n^2 x}$?

What is $\displaystyle\lim_{x\to 0} \sum_{n=2}^\infty \frac{\sqrt{x}\ln n}{1+n^2 x}$ ? Find an asymptotic expansion of $\displaystyle \sum_{n=2}^\infty \frac{\sqrt{x}\ln n}{1+n^2 x}$ as $x\to ...
0
votes
3answers
58 views

Prove or disprove $f(n)$=$2^{n+1}$ is $O(2^n)$

I need to prove or disprove $f(n)$=$2^{n+1}$ is $O(2^n)$. I believe this statement is true, so I want to prove it. I know that $f(n)$ is $O(g(n))$ if there are positive constants $C$ and $k$ such ...
4
votes
2answers
37 views

Show $ \frac{1}{n} \sum_{p \in \mathbb P} \left\lfloor \frac{n}{p} \right\rfloor \log p = \log n + O(1)$

Any hints how to prove for $n \in \mathbb N$ $$ \frac{1}{n} \sum_{p \in \mathbb P} \left\lfloor \frac{n}{p} \right\rfloor \log p = \log n + O(1) $$ where $\mathbb P$ denotes the set of all primes? As ...
2
votes
3answers
36 views

A=LU decomposition time complexity

I am trying to derive the LU decomposition time complexity for an $n \times n$ matrix. Eliminating the first column will require $n$ additions and $n$ multiplications for $n-1$ rows. Therefore, the ...
2
votes
2answers
63 views

Is $\sum_{k=1}^{n-1} \frac{1}{k}\frac{1}{n-k} \sim \frac{\log{n}}{n}$?

I asked a similar question some days ago, but in a more general form that perhaps turned it in a too uninteresting question, so I'm asking it again in a more friendly form. It is true that ...
0
votes
1answer
28 views

Slant asymptote of a function in x and y

After looking for the asymptotes of the function: $y^3+2y^2-x^2*y+y-x+4=0$ I found the answers y=0, y=-x-1 and y=x+1. This is almost exact: the last one should actually be y=x-1. To find the ...
0
votes
1answer
20 views

Why is this horizontal asymptote present and how do I immediately see that from the equation?

This may seem like a stupid question, and I do feel like I should know this. I have been given a simple curve with the following equation and was asked to state the equation of the asymptote of the ...
1
vote
0answers
21 views

asymptotic smooth kernel log(|x-y|)

I am currently trying to show that the function $\log(|x-y|)$ is an asymptotic smooth kernel function, in the sense that: for $x,y \in \mathbb{R}^2$ there exist constants $C_{1},C_{2} > 0$ and an ...
3
votes
0answers
51 views

Do we have a inverse Laplace transform of $\frac{1}{\arctan s}$

Do we have a closed form of this seemingly very simple inverse transformation? If no closed form, what about its asymptotic form? Does this satisfies the criterion to have its inverse ...
2
votes
1answer
31 views

Big O notation - Asymptotics - Question

I want to prove the following$$n - 2\sqrt{n} = \Theta(n)$$ Is it correct to say $$n -1 \leq n \leq n +1 => f(n)=n=\Theta(n)$$ $$\sqrt{n}\leq|-2\sqrt{n}| = 2\sqrt{n}\leq3\sqrt{n} ...
4
votes
1answer
58 views

An asymptotic expansion for $(1 + \frac{x}{n})^n$.

I am trying to work out an asymptotic expansion for the function $$f(x, n) = \left(1 + \frac{x}{n}\right)^n$$ in the following sense. For all $k \geq 1$, let $f_k(x)$ be the function recursively ...
3
votes
2answers
149 views

Euler-Maclaurin Summation

Using EM summation formula estimate $$ \sum_{k=1}^n \sqrt k $$ up to the term involving $\frac{1}{\sqrt n}$ My attempt is $$ \sum_{k=1}^n \sqrt k = \frac{2 \sqrt{n^3}}{3} -\frac{2}{3} + \frac 1 ...
0
votes
1answer
31 views

Find the asymptotic tight bound for $T(n)=T(n-1)+n lg n + n$ and for $T(n)=n^2 \sqrt{n}T(\sqrt{n})+n^5lg^3n+lg^5n$

I am stucked at this problem: Find the asymtotic tight bound for the following recurrences: (Assume that $T(n)$ is constant for sufficiently small $n$) (1) $T(n)=T(n-1)+n lg n + n$ (2) $T(n)=n^2 ...
0
votes
2answers
50 views

Monotone convergence of functions ant theor asymptotic power series

consider a sequence of functions $f_n:(0,\infty)\rightarrow\mathbb{R}$ which are positive and monotone, i.e. $$0< f_1\leq f_2\leq....\leq f_n\leq f_{n+1}...$$ Now let us assume we know the ...