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
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
82 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
278 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
129 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
158 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 ...
4
votes
2answers
34 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
35 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
61 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
50 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
56 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
143 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
24 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)$ ...
0
votes
1answer
24 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 ...
1
vote
2answers
35 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 ...
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} ...
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 ...
2
votes
2answers
37 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
66 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 ...
0
votes
1answer
39 views

What is the asymptotic behavior of the function counting the number of (not necessarily distinct) prime divisors?

From http://en.wikipedia.org/wiki/Arithmetic_function#.CE.A9.28n.29.2C_.CF.89.28n.29.2C_.CE.BDp.28n.29_.E2.80.93_prime_power_decomposition Ω(n), ω(n), νp(n) – prime power decomposition The ...
2
votes
1answer
47 views

Help me approximate this sum: $S = \sum_{j=2}^{N}{\frac{\ln \ln \ln \ j}{( \ln \ln \ j)^2}}$

I would like to figure out the asymptotic rate of growth for the sum $S = \sum_{j=2}^{N}{\frac{\ln \ln \ln j}{( \ln \ln j)^2}}$ in the limit of large $N$. Ultimately, I want to know if $S(N)$ is ...
3
votes
1answer
40 views

In which conditions $ f'(x)=O(g'(x))$ implies $f(x)=O(g(x))$?

First question, let $f,g:(-a,0)\rightarrow(0,\infty)$, introduce the notation: We say $f(x)=O(g(x))$ in $0$, if there exists constants $c,\epsilon>0$, such that $$f(x)\leq cg(x) \ \ \forall ...
2
votes
2answers
51 views

Show that $\sum_{n\le x} \mu ^2(n)=\frac{x}{\zeta(2)}+o(\sqrt{x}) \; (x\to \infty)$

Show that $$\sum_{n\le x} \mu ^2(n)=\frac{x}{\zeta(2)}+o(\sqrt{x}) \; (x\to \infty)$$ I've proven so far that $\sum_{n\le x} \mu ^2(n)=\frac{x}{\zeta(2)}+O(\sqrt{x})$. I want to reduce this error ...
3
votes
3answers
57 views

Bounding $\sum_{k=1}^N \frac{1}{1-\frac{1}{2^k}}$

I'm looking for a bound depending on $N$ of $\displaystyle \sum_{k=1}^N \frac{1}{1-\frac{1}{2^k}}$. The following holds $\displaystyle \sum_{k=1}^N \frac{1}{1-\frac{1}{2^k}} = \sum_{k=1}^N ...
1
vote
1answer
24 views

Asymptotic Distribution of Quantiles

In order to prove that the sample $p$-percentile $x_p, p \in [0,1]$ from a sample of $n$ is asymptotically normally distributed as $n\to\infty$, it is necessary to show the following two limits. They ...
1
vote
0answers
29 views

Power expansion with Big O notation regarding to logarithmic.

I want to know power series expansion calculation using Big O notation. That is $$1-{\displaystyle \frac{x\log^2 (x)}{(x+1)\log^2 (x+1)}}$$ at infinity. Someone calculate easily by using Big O ...
6
votes
1answer
109 views

Asymptotics of $\frac{\sum _{i=0}^{\lfloor n/2 \rfloor} {2(n-2i) \choose n-2i} {n \choose 2i} {4i \choose 2i}}{2^{3n - 1}}$, is it $\frac{2}{\pi n}$?

I am trying to work out the asymptotics of $$\frac{\sum _{i=0}^{\lfloor n/2 \rfloor} {2(n-2i) \choose n-2i} {n \choose 2i} {4i \choose 2i}}{2^{3n - 1}}.$$ My numerical experiments suggest it might ...
1
vote
1answer
23 views

converting asymptotic little-oh into big-oh

Let $f(n)$ be a random function such that $f(n)\cdot n^{1/4-\epsilon}\to 0$ for all $\epsilon>0$. Say we know that $f(n)\cdot n^{1/4}\not\to 0$. Does this imply that $f(n)=\tilde O(n^{-1/4})$? ...
4
votes
3answers
9k views

Family of functions with two horizontal asymptotes

I'm looking for the equation of a family of functions that roughly resembles the sketch below (with apologies for the crudeness of said sketch): Properties I'm looking for: ...
1
vote
1answer
39 views

What is the limit of the below functions when n tends to inifinity?

What is the value for the functions in the image when limit n tends to infinity?. Also what is the asymptotic complexity (big $O$ notation) for all the four functions?. $$\begin{aligned}f_1(n) &= ...
1
vote
0answers
76 views

Sums of Power Law random variables

Suppose $F$ is a Pareto distribution with scale parameter $x_m$ and shape parameter $\alpha$. Assume $X_1, X_2 , \dots, X_n$ are iid random variables drawn from $F$. Let $S_n(k) = X_1 ^k + X_2 ^k + ...
0
votes
1answer
12 views

Big-Oh of $(\log_bn)^c$ is $O(n^d)$

I'm a CS freshman. In my discrete math textbook, it says ... whenever b > 1 and c and d are positive, we have $(\log_bn)^c$ is $O(n^d)$, but $n^d$ is not $O((\log_bn)^c)$ But why? Using ...
0
votes
2answers
41 views

Why does this inequality stand?

I stand that $\log n=O(n^{\epsilon})$ for any $\epsilon >0$. At a previous example we have shown that $$e^{n^{\epsilon}} \geq \frac{n^{\epsilon d}}{d!}$$ where $d=\lfloor ...
4
votes
1answer
63 views

How to use Laplace method to get the asymptotic expansion of multiple integral

I meet difficulty when I try to get the asymptotic behaviour of multiple integral as x tends to plus infinity. And $-1<$p$<1$ $$\int_x^{+\infty}\int_x^{+\infty}e^{-{\frac{1}{2\sigma^2(1-p^2)}\ \ ...
9
votes
1answer
91 views

An upper bound for Summative Fission numbers

I recently found OEIS entry A256504 and have been playing around with this sequence a bit. Its definition is: For a positive integer $n$, find the greatest number of consecutive positive integers ...
5
votes
2answers
106 views

How to get the asymptotic form of this oscilatting integral?

So the integral is like this: $$\int_1^\infty \frac{\cos xt}{(x^2-1)\left[\left(\ln\left|\frac{1-x}{1+x}\right|\right)^2+\pi^2\right]}\mathrm{d}x$$ The question is how to get the asymptotic form of ...
2
votes
1answer
44 views

Show that $f(x) = O(1/x)$

Let $f:\mathbb{R}\to\mathbb{R}$ such that $f\ge 0$, monotonically decreasing and $\int_0^\infty f(x) \ dx < \infty$. Prove that $f(x) = O(1/x)$. So basically, both $f(x)$ and $1/x$ are ...
1
vote
2answers
60 views

Divide and Conquer in big O notation

I've got a problem – divide-and-conquer part of my program divided my problem into 2 parts: 1/7 and 5/7 of a problem + merging in a linear time. I need to know it's asymptotic complexity. I know, it ...
4
votes
1answer
104 views

Is $\sum_{k\leqslant n} f'(k)f'(n-k) \asymp f'(n)f(n)$ when $f'$ is positive decreasing?

In this answer of a question of mine, the user Homegrown Tomato gave a nice argument that somewhat shows that $$\int_{\substack{t+s\leqslant x \\ t,s \geqslant 0}} f'(t)f'(s)dtds \asymp ...