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
23 views

comparing expressions confusion

This formula is actually from a big $O$ notation example, but I am confuse about the mathematical formula. I read that: if $n$ and $c$ are $1$, $3n^2 - 100n + 6$ is not a big o of $n^3$ or $cn^3 ...
2
votes
0answers
44 views

asymptotic expansion of hermite functions

Does anybody know how to proof the first asymptotic expansion of this page: http://en.wikipedia.org/wiki/Hermite_polynomials#Asymptotic_expansion ? (and how the physicist use this asymptotic ...
3
votes
1answer
103 views

$\sum \limits_{n \geq 0}a_n \frac{x^n}{n!}=e^{x+x^2/2}$ implies $a_n \sim \frac1{\sqrt2} n^{\frac n2}e^{ -\frac n2+\sqrt n -\frac14 }$

Prove the following asymptotic formula for the exponential generating function coefficients of $e^{x+x^2/2}$: $\; \; a_n \sim \frac1{\sqrt2} n^{\frac n2}e^{ -\frac n2+\sqrt n -\frac14 }$ Stanley ...
2
votes
1answer
52 views

is there a concept of asymptotically independent random variables variables?

To prove some results using a standard theorem I need my random variables to be i.i.d. However, my random variables are discrete uniforms emerging from a rank statistics, i.e. not independent: for ...
3
votes
3answers
76 views

Complete elliptic integral of the first kind $K(m)$ asymptotc expansion at $m = -\infty$

What is the asymptotic behavior of $K\left(-\frac{1}{\delta^2}\right), \delta > 0$ when $\delta$ tends to zero? Here $$ K(m) = \int\limits_0^{\pi/2} \frac{d\theta}{\sqrt{1 - m\sin^2 \theta}}, $$ ...
1
vote
2answers
31 views

Is this inductive big O proof possible / Does this question make sense?

Prove that $\sum_{i=j}^k \frac 1i$ is $O(\ln(k)-\ln(j-1))$ using induction for all $i$. The way I understand this question, it's nonsense - $i$ is the iteration variable, not something that can be ...
0
votes
2answers
32 views

Analysis of Algorithms - Big O Notation Equivalences - Limits

Please see below block question from review for test. True Or False? Justify Your answers A) is 2^(n+1) = O($2^n$) B) is 2^2n = O($2^n$) C) is log($n^2$) = O(logn) D) is ...
0
votes
0answers
13 views

WKB for a sixth order eigenvalue problem

I have the following 6th order eigenvalue problem: $$ (D^2 - \alpha^2)^3 y(x) = -\alpha^2 \lambda Q(x) \, y(x), \quad 0 < x < 1, \quad \text{+ BCs}, $$ where $D = \mathrm{d}/\mathrm{d} x $, ...
0
votes
0answers
38 views

Boundary layer problem

This question is taken from Bender & Orszag "perturbation methods" $y' = (1 + X^{-2}/100)y^2 - 2y + 1$ ,$y(1)=1$ first we can see that if we set $\epsilon=100x^{2}$ we can translate the above to ...
1
vote
1answer
40 views

Interpreting little-$o$ notation

This is the integrand of a complex integral: $$\frac{o(\zeta - z)}{\zeta - z}$$ The ensuing discussion says that this can be made as small as desired [by confining $\zeta$ close to $z$]. In general ...
3
votes
2answers
73 views

Question about steps/derivation regarding Laplace method.

I am reading something on the Laplace method of integrals and I don't understand part of it's argument. It gives the integral $$\int_{-3}^4 e^{-\lambda x^2}\log(1+x^2)dx$$ and finding the leading ...
3
votes
3answers
70 views

Wouldn't each addition take time $O(n)$?

I am going over the asymptotic runtime of regular matrix multiplication. Here is a lecture slide I am referencing(too much to type out, shown below), from Algorithms Everything makes sense up ...
1
vote
0answers
24 views

help with an asymptotic for a certain product

I'm having difficulty finding an asymptotic formula for the following product: $$ k^{\alpha}\prod_{1 \leq i \leq N \atop i \neq k} (i^{\alpha}-k^{\alpha})$$ where $N$ is a parameter tending to ...
0
votes
1answer
18 views

Asymptotic expansion for the inverse of a matrix-valued function

suppose I have an asymptotic expansion for a matrix-valued function $\psi : \mathbb{C} \to \mathbb{C}^{2 \times 2}$ : $$\psi(\lambda) \sim I + \frac{m_1}{\lambda} + \frac{m_2}{\lambda^2} + \cdots \ \ ...
0
votes
0answers
31 views

Runtime Complexity | Recursive calculation using Master's Theorem

I have the following recurrence relation (arising from some kind of augmented merge sort): $$ T(n) = T\left({2n\over5}\right) + T\left({3n\over5}\right) + n$$ and I need to find the worst-case ...
1
vote
1answer
86 views

Find upper bound time complexity of recurrence function using iterative method

I want to find the upper bound time complexity of this function. I know how this is done using the induction method, but I can't find clear steps on how to solve it using the iteration method. ...
3
votes
0answers
19 views

Big-O Notation exponentials

I'm learning about Big-O notation for algorithm runtime, and I need some help understanding one part. I read that for the constant, c, does not matter as the function increases rapidly. Does that ...
2
votes
0answers
21 views

Determining asymptotics of a function given a series of difference-like inequalities

I have a function $f: \mathbb{R}_{\geq 0} \rightarrow \mathbb{R}_{\geq 0}$ and I know it satisfies the following properties. $f(x) \leq \frac{\log{\sqrt{2}}}{2x}$ and for all $A \geq 1$ and $B \geq ...
1
vote
1answer
55 views

Approximation of combination $ {n \choose k} = \Theta \left( n^k \right) $?

Is it a valid to say $$ {n \choose k} = \Theta \left( n^k \right) $$ for any $n$ and $k$? If so, how to prove it? Note: $k$ is not a function of $n$. Note: Observed it here (page 5): ...
0
votes
0answers
28 views

how to estimate $\sum (n,i)$?

How to estimate $\sum\limits_{i=-A}^{A} \binom{n}{i}$ ? This probably relates to the central limit theorem and the proof of it. But I want good estimates, also for small values (not just limits to ...
1
vote
0answers
22 views

Prerequisites to reading *Convergence of Probability Measures* by Patrick Billingsley.

I want to improve myself in asymptotic theory regarding the realm of probability. I tried reading Convergence of Probability Measures by Patrick Billingsley but right off the bat the De ...
1
vote
1answer
31 views

Elementary proof of an estimate on $\zeta$

I saw somewhere that If $s=\sigma +it$ where $\sigma >0$ and $t\in \mathbb R$,$x\geq |t|/\pi\implies \zeta(s)=\displaystyle \sum_{n\leq x} \frac{1}{n^s}+\frac{x^{1-s}}{s-1}+O(x^{-\sigma})$ ...
1
vote
0answers
37 views

What does $\mathbb P(\overline{\mathbf X} = \mathbf x)$ mean

I am reading Peter Hall's "the bootstrap and edgeworth expansion". In Theorem 2.3 on page 57, it claims that if the characteristic function $\chi$ of a $d$-dimension random variable $\mathbf X$ ...
4
votes
1answer
100 views

Method of Steepest descents integral

I am looking to evaluate the following asymptotic integral: Find the leading term of asymptotics as $\lambda\to\infty$ $I(\lambda)=\int_0^1\cos(\lambda x^3)dx$ Using method of steepest descents ...
15
votes
1answer
152 views

If $p$ is a positive multivariate polynomial, does $1/p$ have polynomial growth?

I wanted to ask a separate question to focus on an elementary issue from my question Does the inverse of a polynomial matrix have polynomial growth?. Let $p : \mathbb{R}^n \to \mathbb{R}$ be a ...
2
votes
1answer
116 views

Show that $1/\zeta(2k) = \sum_{m \le K} \mu (m)/m^{2k} + O(1/K)$

Show that $1/\zeta(2k) = \sum_{m \le K} \mu (m)/m^{2k} + O(1/K)$. I have already proved that $1/\zeta(s) = \sum_{m=1}^{\infty} \mu (m)/m^s$. But how do I show that if $k\ge 1$, $1/\zeta (2k) = ...
1
vote
0answers
35 views

A combinatorial way to understand $\sum \log^2 n $

Stirling's formula has many derivations using the factorial function: $$ \log N! = \sum_{n=1}^N \log n = \sum_{n=1}^N \sum_{m=1}^n \bigg( \log m - \log (m-1) \bigg) = \sum_{n=1}^N \sum_{m=1}^n - ...
0
votes
0answers
44 views

Approximation of integral as integral range tends to 0

I would like to approximate $\int_{0}^{x}t^{-2}e^{t}\mathrm{d}t$ (maybe find the first two terms) as $x\rightarrow0$. I can't seem to do it by "divide and conquer" or any method. Any suggestion would ...
0
votes
0answers
10 views

Code that Creates a Monotonic Array

I'm not sure whether this belongs on StackOverflow or here. Suppose I have an infinite (indexed from $-\infty$ to $\infty$) array of random doubles x[]. They are ...
0
votes
1answer
28 views

Stokes phenomenon of the Airy function

I am now trying to understand what the so-called stokes phenomenon means. In this page Stokes phenomenon, it reads that `` For large $x$ of given argument the solution (of the Airy equation)can be ...
0
votes
2answers
27 views

Finding the roots and the rescaling of an equation

This question is taken from Hinch's book on perturbation. I need to find the rescalings $x=\delta X$ and the roots of the equation $\epsilon^2x^3+x^2+2x+\epsilon=0$ I have found to possible ...
0
votes
0answers
29 views

Long division for multipolynomial expression, little o notation

I have this expression: $$\mathrm{Exp}=\frac{d^3(-12a^4)+d^2(4a^4-16a^3)+d(4a^3-6a^2-a)}{d^3(-12a^4+12a^3)+d^2(4a^4-20a^3+16a^2)+d(4a^3-11a+7a)+(1-2a+a^2)}$$ Is there any way I can take the second ...
0
votes
1answer
63 views

What algorithm can sort the first sqrt(n) elements of an array in O(n) time?

I want to partially sort an array of $n$ elements to get the first $\sqrt{n}$ elements sorted, and it has to be done in $O(n)$ time. The complexity $O(n)$ seems to imply that it is necessary to go ...
0
votes
0answers
14 views

(Empirical likelihood method) Find the order of a parameter given a set of constraints

Firstly we assume that $X_1,...X_n$ are order statistics($X_i\leq X_{i+1}$) from an i.i.d sample of random variables and let $r$ be integer and $r\geq1$. Start with the equation (1) \begin{equation} ...
2
votes
1answer
39 views

Evaluating the leading term of asymptotics

I am struggling with this problem where we're asked to use Laplace's method: Find the leading term of the asymptotics of the following intergral for $\lambda\to\infty$: $$\int_0^{\infty} ...
2
votes
0answers
23 views

Asymptotics of Laplace transform at minus infinity

I am interested in relating the asymptotic behavior of a function $f(t)$ for large values of $t$ with the asymptotic behavior of its Laplace transform $\hat{f}(s)$ for small values of $s$. In practice ...
-1
votes
1answer
93 views

Multiplying logarithms of different bases [closed]

How do you multiply the following logs... $$\log_5(n) * \log_2(n)$$
8
votes
1answer
210 views

Complexity $O(n^3)$ vs $O((\log n)^4))$

I would like to prove that $O(n^3)$ is bigger than $O((\log n)^4)$. I thought that I can divide both powers with 4 so it is $$O\left(n^{\frac{3}{4}}\right)$$ vs $$O(\log n)$$ but then I don't know ...
1
vote
0answers
20 views

Show that $f(b^i n) \le c^i f(n)$

Let $f$ be a b-smooth function. Let $c$ and $n_0$ be constants such that $f(b n) \le c f(n)$ $\forall $ $n \ge n_0$. Show that $\forall $ $ i \in \mathbb{N}, f(b^i n) \le c^i f(n)$ I thought I should ...
1
vote
1answer
90 views

Integrate 1/ln(ln(x)) asymptotically

I was looking for the asymptotic behaviour of the anti-derivative of $\frac{1}{\ln \ln x}$, in terms of the big-O notation. Wikipedia's list does not have this integral, and Wolfram Alpha says "no ...
2
votes
2answers
80 views

How to find a function that is the upper bound of this sum?

The Problem Consider the recurrence $ T(n) = \begin{cases} c & \text{if $n$ is 1} \\ T(\lfloor(n/2)\rfloor) + T(\lfloor(n/4)\rfloor) + 4n, & \text{if $n$ is > 1} \end{cases}$ A. Express ...
2
votes
1answer
41 views

Largest possible subset primes

Let $q$ be a Sophie Germain prime number, i.e. $2q+1=p$ is prime. Consider the set $\{1,2,3,\ldots,p-1\}$. Then what is the maximum size of a subset of this set, such that the subset contains no two ...
13
votes
1answer
263 views

Asymptotic expression of $\int_{- D}^{D} \frac{\text{tanh}(\xi)}{\xi -\omega}\mathrm{d}\xi$

How to derive the following asymptotic expression ($|\omega| \ll D $)? $$P.V.\int_{- D}^{D} d\xi \frac{\tanh(\beta \xi)}{\xi -\omega} \approx 2 \ln\left(\frac{D}{\sqrt{\omega^2+T^2}}\right),\ \ \ ...
2
votes
0answers
35 views

The series may converge, but what about the series / n?

Let $a_i$ be a positive sequence such that $a_i \to 0$. I know that the series $\sum_{i=1}^\infty a_i$ may be divergent. But what about the series divided by $n$; does the following go to 0? ...
1
vote
1answer
27 views

About the equivalence of two asymptotic probabilistic statements

Let $g(n)$ be some monotone increasing function of naturals, and let $X_n$ be a sequence of positive random variables. Consider the following two claims: Claim 1. $\exists f=o(g(n)),\ ...
6
votes
0answers
52 views

Show that $1^k+2^k+…+n^k$ is $O (n^{k+1})$.

Let $k$ be a positive integer. Show that $1^k+2^k+...+n^k$ is $O (n^{k+1})$. So according to the definition of big-$O$ notation we have: $$1^k+2^k...+n^k ≤ n(n^k) = n^{k+1}$$ whenever $n>1$ Is ...
0
votes
3answers
68 views

Show that $(x^3+2x)/(2x+1)$ is $O(x^2)$

Show that $(x^3+2x)/(2x+1)$ is $O(x^2)$ The definition says: We say that $f(x)$ is $O (g(x))$ if there are constants $C$ and $k$ such that $$\mid f(x) \mid \leq C \mid g(x) \mid$$ whenever $x > ...
0
votes
0answers
28 views

uniform limits and asymptotic equivalence

I am told that $\frac{f(\lambda r)}{f(r)}$ tends to 1 uniformly in $\lambda$. I also know that $x(t)$ is asymptotically equivalent to $ct$, so $x(t)\sim ct$. How can I show that $\frac{f(x(\lambda ...
1
vote
0answers
39 views

Asymptotic Formula for Sum

I am trying to find an asymptotic formula for the sum of the following: $\sum _{x=1}^{\infty } x \left(\left(1-\frac{\Gamma (x,\lambda )}{\Gamma (x)}\right)^n-\left(1-\frac{\Gamma (x+1,\lambda ...
0
votes
1answer
19 views

natural logarithmic to asymptotic order

Say we have an equation $\lambda_{\epsilon}(s)=-\frac{1}{\pi s^2}\ln(1-\epsilon)$ $\forall s\in (0,(M \mathcal{k})^{-\frac{1}{\alpha}})$ where $s$ can be obtained by $s=(M ...