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

learn more… | top users | synonyms (1)

4
votes
2answers
118 views
+50

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
17 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
26 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
63 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 ...
1
vote
0answers
15 views

does an exponential bound on a Lyapunov candidate implies asymptotic stability?

if I have a Lyapunov candidate $V:[0,\infty)\rightarrow \mathbb{R}$ and I'm able to show that $$ V(t)\le k e^{-\eta t} V(0),\qquad \forall t\in[0,\infty) $$ can I conclude something about ...
2
votes
1answer
46 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
68 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 ...
8
votes
5answers
174 views

The maximal size of between $\varphi(n)$ divided by $\lambda(n)$.

I want to find $$f(n) = \max\left\{\frac{\varphi(k)}{\lambda(k)} : 1 \leq k \leq n\right\}$$ In other words, I want to find the maximal value of $\frac{\varphi(k)}{\lambda(k)}$ when $k$ is ...
1
vote
1answer
43 views

How to prove that $\log(n)$ is $O(n^c)$? [on hold]

What's a straightforward way to prove that? For any c>0.
0
votes
1answer
22 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
60 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}}$, ...
-3
votes
0answers
35 views

Show that $\log_ax \in \operatorname{\Theta}(\log_bx)$ [closed]

Suppose $a$ and $b$ are greater than $1$ and that $f(x) = \log_ax$ and $g(x) = \log_bx$. Prove $f \in \operatorname{\Theta}(g)$. Edit: I fail to see how this is off-topic. This is the entire ...
1
vote
0answers
21 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
48 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
78 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
16 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
639 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. ...
4
votes
1answer
453 views

Can a curve be an asymptote?

$f(x)=x^3+\frac{3}{x-1}$ This was the question given to me.I replied that $f(x)$ will have only a single vertical asymptote of $x=1$. My teacher told that there'll be be two asymptotes.One is the ...
0
votes
1answer
19 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
47 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
25 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
9 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)= ...
7
votes
0answers
100 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
36 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
52 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
18 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
33 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
98 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
37 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
78 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
37 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
263 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
123 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
127 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
55 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 ...
3
votes
2answers
30 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
30 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
58 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
45 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
54 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 ...
2
votes
2answers
136 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 ...
2
votes
0answers
23 views

Optimizing an asymptotic recurrence relation with two recursive terms

I have a recurrence relation that looks like this: $T(n) = 2 T(c n) + T((1-c)n) + O(1)$ The base case is just $T(b) = 1$ when $b \leq 1$. I'm trying to figure out the best value of $c \in (0, 1)$ ...