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

Inverse of $x^x$ [duplicate]

Since $x^x$ grows very fast, its inverse should accordingly grow very slow, possibly slower than $\ln(\ln(x))$. I am troubled with finding such an inverse: I only get to the point: $\ln(x)x=\ln(y)$ ...
1
vote
1answer
58 views

Evaluate $\int_{x=0}^{\infty}\left(\frac{1}{\sqrt{x}}(1-e^{-x})\right)^{M-1}e^{-x}(1+sx)^{-N}dx,$

I am trying to evaluate $$\int_{x=0}^{\infty}\left(\frac{1}{\sqrt{x}}(1-e^{-x})\right)^{M-1}e^{-x}(1+sx)^{-N}dx,$$ where $s>0$, $M$ and $N$ are positive integers. But seem that the above integral ...
2
votes
2answers
26 views

Does one of these conditions on a sequence imply the other one?

Let ${(r_n)}_{n \geq 0}$ be a sequence of integers $\geq 2$. Set $q_n=\prod_{i=0}^{n-1} r_i$ (agreeing with $q_0=1$). I want to know whether one of these two conditions implies the other one (I think ...
1
vote
3answers
64 views

Upperbound confusion

Why is the following true? $3n^2-100n+6$ is big $O$ of $n^2$ This has been demonstrated to be true when $c$ is $4$ and $n$ is $10$. $3*100-1000+6 = -694 = 694$ is the absolute value is a big $O$ of ...
2
votes
2answers
48 views

Large $a$ asymptotics of $\int_0^{\pi/4} \exp(-a(x^2-\frac{x^4}{3}))$

I'm looking for a way to prove that $\displaystyle \int_0^{\pi/4} \exp(-a(x^2-\frac{x^4}{3}))dx=\int_0^{\pi/4} \exp(-ax^2)dx+o\left(\int_0^{\pi/4} \exp(-ax^2)dx\right)$ as $a$ goes to $\infty$ ...
1
vote
0answers
27 views

Proof $\log(cn)$ is in $\Theta(\log(n))$

How can I prove that $\log(cn)$ is in $\Theta(\log(n))$, where $c$ is a constant? I tried to prove $c_1\log(n) \le \log(cn) \le c_2\log(n)$, where $c_1$ and $c_2$ are also constants, but I'm having ...
1
vote
3answers
37 views

Show that $\lim_{n\to\infty}\frac{n}{(\log n)^2}=\infty$

I am working on an asymptotic analysis question from a data structures past paper, and I need to show that $$\lim\limits_{n\to\infty}\frac{n}{(\log n)^2}=\infty$$ Could I have a hint for working out ...
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}}, $$ ...
0
votes
0answers
17 views

Expected size of largest connected component in a binary matrix

Let $C_4(\mathbf M)$ and $C_8(\mathbf M)$ denote the size of binary matrix $\mathbf M$'s largest 4-connected component and 8-connected component of the same value, respectively. For example, the ...
3
votes
1answer
77 views

A proof involving an infinite sum

I am trying to prove that there exist constants $C_1 > 0$, $C_2>0$ such that$$C_1 \log N \geq\sum_{k=1}^\infty(1 - (1- 1/2^k)^N) \geq C_2\log N$$ where $N\in Z^+$. Could you please give me ...
0
votes
2answers
36 views

Show that $\sin(\mathcal{o}(x)) = \mathcal{o}(x)$ as $ x\to 0$

So I want to show that $\sin(\mathcal{o}(x)) = \mathcal{o}(x)$ as $ x\to 0$. So far I have thought that my result will come from showing $ \displaystyle \Big|{\frac{\sin(f(x))}{x}}\Big| \to 0$ as ...
7
votes
0answers
51 views

Decay of amplitude integral

Consider the function $$ f(\vec{x}) = \int_{\Bbb R^3} {\frac{ e^{-i\,\vec{x}\cdot\vec{k}}}{\sqrt{\vec{k}^2 + m^2}}} d^3 k $$ from Zee's Quantum Field Theory in a Nutshell. He argues like this: ...
1
vote
3answers
49 views

$N^{1/2}$ and randomness

I apologize if this question is overly vague, but part of the reason I am asking is because I don't know a more precise way of discussing these ideas. To state a general question: What, if any, ...
2
votes
1answer
194 views

Prove or disprove the Big-O of an exponential function

$f(n) = 2^{n+1} = O(2^n)$ Intuitively, I think the statement is false. However, when I go about disproving it, I find that $2^{n+1} = 2^n \cdot 2$, meaning that if there is a constant $C$ larger than ...
0
votes
0answers
33 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 ...
2
votes
2answers
42 views

$\int_2^x\frac{dt}{\log^kt}=O\left(\frac{x}{\log^kx}\right)$

I seek to prove the identity $$\int_2^x\frac{dt}{\log^kt}=O\left(\frac{x}{\log^kx}\right)$$ I was given the following hint: Split the integral into $\int_2^{f(x)}+\int_{f(x)}^x$ for a ...
1
vote
1answer
41 views

Compute $(\ln(n!))^2$

In a discrete mathematics past paper, I must solve the following problem: We know (from the Stirling approximation) that ...
1
vote
1answer
23 views

Asymptotics of $(\cosh(x+c)-\cosh(c))^{-\frac{1}{2}}$

let $c>0$ be a constant and consider the function $$\frac{1}{\sqrt{\cosh(x+c)-\cosh(c)}}, x>0.$$ I'm wondering how the asymptotic expansion for $x\downarrow 0$ look like!? In case of $c=0$ the ...
0
votes
0answers
12 views

Graphs Approaching Asymptotes

I've been wondering this for a while. For graphs that approach asymptotes, are there certain formulas that can determine the distance between the graph and the asymptote as $x$ gets infinitely small ...
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 ...
2
votes
0answers
24 views

Approximation of Hermite functions

I'm looking for an "easy" proof of the asymptotic expansion of Hermite functions ($f_n(x)=H_n(x)e^{-x^2/2}$ where $H_n$ is the Hermite polynomials). The asymptotic expansion is $$ f_n(x) \sim_{n ...
0
votes
0answers
35 views

How to asses the order of combinations

Let $\{a_i\}_{i=1}^m$ be some increasing sequence, bounded away from zero. How to see that as $n\to\infty$, we obtain $$\begin{pmatrix} n\\ m \end{pmatrix}^{-1}\sum_{i=1}^m\begin{pmatrix} ...
1
vote
0answers
35 views

Two-term asymptotic approximation for roots of a polynomial (dominant balance)

I'm trying to find the roots to the following equation: $t^5 - \epsilon t^3 + \epsilon^3 = 0$ as $\epsilon \rightarrow 0$. From expansion $t= \epsilon^{\alpha}t_1 + \epsilon^{2\alpha}t_2 + ...
17
votes
2answers
880 views

Showing that $\lim_{n\to\infty}\sum^n_{k=1}\frac{1}{k}-\ln(n)=0.5772\ldots$

How to show that $$\lim_{n\to\infty}\left[\sum^n_{k=1}\frac{1}{k}-\ln(n)\right]=0.5772\ldots$$ No clue at all. Need help! Appreciated!
0
votes
1answer
16 views

$ n - \sqrt{n}$ $\Theta$ Complexity

$ n - \sqrt{n} \leq n - \sqrt{n} + \sqrt{n}=n=O(n)$ But I don't know what I should do about $\Omega(.) , \Theta(.)$ Should I try to solve it with lim?
5
votes
1answer
59 views

Decay of Fourier Transform

I encountered the following statement, and I cannot see why it is true(if it is). Suppose $f$ is a nonnegative, bounded, compactly supported and measurable function with the following properties: ...
0
votes
0answers
14 views

Additive error in Stirling's Approximation

I know that Stirling's Approximation is asymptotic to $n!$ as in the ratio approaches $1$ (which is the definition). But as far as I have noticed, the additive error diverges. Is this a common ...
3
votes
1answer
30 views

Trapezoidal Rule in Stirling's Approximation

https://en.wikipedia.org/wiki/Stirling's_approximation Here $$\sum \limits_{i=1}^n log(i) $$ is approximated as $$\int^n_1log(x) dx\ +\ 1/2\ log(n)$$ but I would approximate it as ...
4
votes
3answers
656 views

Formally proving that a function is $O(x^n)$

Say I have a function \begin{equation*} f(x) = ax^3 + bx^2 + cx + d,\text{ where }a > 0. \end{equation*} It's clear that for a high enough value of $x$, the $x^3$ term will dominate and I can ...
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),\ \ \ ...
0
votes
0answers
48 views

Node potentials of minimum cost flow successive shortest path algorithm

I have a simple directed graph $G(V,E)$ that has a source $s$ and sink $t$. Each edge $e$ of $G$ has positive integer capacity $c(e)$ and positive integer cost $a(e)$. I am trying to find the minimum ...
0
votes
0answers
28 views

Prove or provide a counter example: $f(n) \notin o(g(n))$ and $f(n) \notin \omega(g(n)) \implies f(n) \in \theta (g(n))$

$f(n) \notin o(g(n))$ and $f(n) \notin \omega(g(n)) \implies f(n) \in \theta (g(n))$ Without giving me the answer, please tell me how would you manipulate this? I know that $f(n) \in \theta (g(n)) ...
3
votes
2answers
44 views

Limit with polylog

How do you show the following limit? $$\lim_{x\to\infty} x\log(-e^x + 1)+\operatorname{Li}_2(e^x)-\frac12x^2=\frac{\pi^2}3$$ Where $\operatorname{Li}_n(x)$ is the polylogarithm. This question is ...
0
votes
0answers
34 views

Asymptotic analysis of Integrals of powers of sine and their application to intersections of hyperspheres

I am trying to estimate the probability of an event in an algorithm. For simplicity, assume there are two hyperspheres of radius $r$, at a distance $r$ from each other. I am looking to see how the ...
4
votes
1answer
70 views

Closed form or asymptotic expansion for $\int_0^m \frac{n^x}{\Gamma(x+1)}dx$?

$$\int_0^m \frac{n^x}{\Gamma(x+1)}dx:n,m \in \mathbb{R}$$ I'm dubious as to whether there's a closed form for the above, if there is I'll be very happy. Otherwise: Is there a closed form for ...
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 ...
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 ...
3
votes
1answer
111 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 ...
1
vote
0answers
38 views

Using singularity analysis to find the main asymptotic term of the Catalan Numbers

Using singularity analysis to find the main asymptotic term of the Catalan Numbers \begin{align} C_n = [z^n]\frac{1-\sqrt{1-4z}}{2z} \end{align} Can someone please explain to me the general concept ...
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 ...
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 ...
6
votes
1answer
3k views

Formal definition of big-O when multiple variables are involved?

(My apologies if this is a duplicate; I did some searching but didn't turn up anything else like this on the site. Please let me know if it's a duplicate and I'll gladly delete it.) I was reading up ...
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
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 $, ...
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) = ...
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 ...
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
votes
1answer
200 views

Asymptotic behavior of the solution of $x^4 \frac{d^2y}{dx^2}+ \frac{1}{4}y=0$ near $0$

Can you help me find the leading asymptotic behaviors about the irregular singular point $x=0$ of $$x^4 \frac{d^2y}{dx^2}+ \frac{1}{4}y=0$$ So far I have got $y(x) = ...
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 ...