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
0answers
22 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
62 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 ...
1
vote
1answer
40 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
0answers
20 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 ...
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
1answer
44 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 [on hold]

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 ...
-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 ...
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.
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
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 ...
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)= ...
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 ...
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)= ...
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, ...
1
vote
1answer
51 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
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 ...
8
votes
5answers
172 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 ...
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
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 ...
0
votes
1answer
35 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 = ...
7
votes
0answers
99 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: ...
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 ...
4
votes
3answers
126 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
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
1
vote
2answers
31 views

Slow decreasing function that exhibits asymptotic behaviour.

I am currently doing some work on modelling the effects of treated nets usage on mosquito populations. Nets do not retain their maximum efficacy forever. They lose their chemical efficacy after about ...
0
votes
1answer
22 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 ...
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 ...
3
votes
1answer
52 views

What are the bounds (upper and lower) for $|A+A|$?

Let $A$ be a finite set of real (or complex) numbers. If I consider sets with small sizes, we have that: If $A$ is the empty set, then $A+A$ is also empty. If $A$ is a singleton, then $A+A$ is ...
1
vote
2answers
46 views

Unusual 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} ...
0
votes
2answers
49 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 ...
2
votes
2answers
35 views

Help with recurrence $T(n) = T(n/2) + n$

I just need help seeing where I went wrong in this solution. $$T(n) = T\left(\frac{n}{2}\right) + n,~~~ T(1) = 0$$ By master theorem, this is $\theta(n)$. However, when I try to solve it, it ...
1
vote
1answer
34 views

How can I prove $n - 2\sqrt{n} = \Theta(n)$

I want to prove the following $$n - 2\sqrt{n} = \Theta(n)$$ It's $n - 2\sqrt{n} \leq n = O(n)$ How can I prove the same for $\Omega(n)$
-2
votes
2answers
65 views

Find witnesses proving that $f(x) = 2x^3 + x^2 + 5$ is $O(x^3 )$. [closed]

Find witnesses proving that $f(x) = 2x^3 + x^2 + 5 \textrm{ is } \mathrm{O}(x^3 )$. What do i need to do here? Like step by step?
0
votes
1answer
22 views

Asymptotes and their like

Can an asymptote be a curve? From what I have read, it suggest that the numerator must strictly be only one degree higher than than the denominator. However mathematically speaking, a equation like ...