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
2answers
44 views

Does $O(\log^2(x))$ imply $O(x)$

Does $O(\log^2(x))$ imply $O(x)$ I have to prove the following: $$\sum\limits_{\substack{n\in\mathbb N\\n\le x}}\Lambda(n)\log(n)=\psi(x)\log(x)+O(x)$$ Applying partial sum I get; ...
4
votes
1answer
406 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
0answers
6 views

Deriving information about asymptotics from finitness of a limit

Let $f_1,f_2:\mathbb{R}\setminus\{0\}\to \mathbb{R^+}$ be two $C^1$ functions and $\alpha:\mathbb{R}\setminus \{0\}\to \mathbb{R}$ be a function from a Zygmund class (in particular it is Holder for ...
0
votes
0answers
14 views

How to solve asymptotic recurrence without using Master Theorem

I am working on the following problem. Consider the function $B:\mathbb{N}\to\mathbb{R}$ defined by: $$B(n) = \begin{cases} 1 & \text{if $n\leq 2$,}\\ 3\cdot B(\lceil n/\log_2 n\rceil) + n & ...
4
votes
1answer
44 views

Product of two sets with density zero has density zero?

Let $A$ and $B$ be two subsets of $\mathbb N$ which have asymptotic density zero. Define $A\times B$ as the set of integers of the form $ab$ with $a\in A$ and $b\in B$. Must $A \times B$ also have ...
4
votes
1answer
38 views

Order of Growth of a Sum

Let $n>k$ and $r$ be arbitrary positive integers. Define $q=k/n$. I want to show that $$ \sum_{i=0}^{rk} \binom{rn}{i}q^i(1-q)^{rn-i}(rk-i)=\Theta(\sqrt{r}) $$ as $r\rightarrow \infty$. I've ...
0
votes
1answer
38 views

Why is $1 - \cos(x)$ of $\mathcal{O}(x^2)$?

I know the definition of order estimates, For the solution to apply we need to show: $ \displaystyle\lim_{x \to 0} \frac{1 - \cos(x)}{x^2} = A \neq 0\space or \space \infty$ But how can one show ...
2
votes
2answers
109 views

Approximation of binomial distribution with normal distribution

The Central Limit Theorem implies that near the center of mass we can approximate the binomial distribution with the normal distribution: $$ P(B(n,p) \geq i) \approx P(Z \geq \frac{i - n p}{\sqrt{n p ...
1
vote
2answers
12 views

Horizontal and Vertical Asymptotes of functions

So I'm completing a chart analyzing the different properties of three different functions: $f(x)=\log(x^2+6x+9), g(x)=\sqrt{x^2 -1}$ (sorry not sure how to do square roots on here), $h(x)=f(x)(g(x))$ ...
1
vote
1answer
31 views

Asymptotic of a complex integral

Consider the following integral $$f(x):=\int_x^{+\infty}re^{-(r+ir^2)}dr$$ I want to understand the asymptotic behavior of $f(x)$ as $x\rightarrow +\infty$ Thank you for any suggestion.
0
votes
1answer
87 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
53 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
23 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
61 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
46 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
25 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
36 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
64 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
14 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
62 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
43 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
44 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
175 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
21 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
36 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
40 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
11 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
2answers
33 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 ...
1
vote
0answers
20 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
30 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
32 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
848 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
13 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
53 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
12 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
24 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
650 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
248 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
19 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
22 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
41 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
32 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
143 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
89 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
36 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
39 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 ...