Questions tagged [asymptotics]
Questions involving asymptotic analysis, including growth of functions, Big-$O$ notation, Big-$\Omega$ and Big-$\Theta$ notations.
7,331
questions
0
votes
0answers
4 views
Given a half-space Fourier transform what asymptotic conclusion can we make about $f(x)$?
If we have a half-space Fourier transform $\tilde{f_{+}}(k)$ of $f(x)$ satisfying $\tilde{f_{+}}(k) =\mathcal{O}(k^{-3})$ for $k \to \infty$ what asymptotic conclusions can we say about $f(x)$?
I'm a ...
0
votes
0answers
37 views
Approximating $\int_0^{\pi/4}\cos(x t^2)\tan^2t \ \mathrm{d} t$?
I am trying to find the leading order term for this integral using a stationary phase approach: $\int_0^{\pi/4}\cos(x t^2)\tan^2t \ \mathrm{d} t$. Using Euler's formula, the integral is the real part ...
-1
votes
0answers
9 views
Remove logarithms from the solutions in form of Frobenius Series
A singular point $x_0$ of a homogeneous linear differential equation is said to be isolated if the coefficient functions are singular at $x_0$ and are single-valued analytic functions in a punctured ...
1
vote
0answers
34 views
asymptotic solution of recurrence relation
can you help me to solve this recurrence equation asymptotically?
my recurrence relation is
$f\left(n\right)=f\left(\frac{n}{3}\right)+f\left(\frac{n}{6}\right)+\left(n\right)^{\sqrt{\log\ n}}$
I ...
1
vote
0answers
12 views
transform a general linear second-order equation into the hypergeometric equation
Show that a general linear second-order equation with three regular singular points at 0, 1, and $\infty$ and no other singular points can be transformed into the hypergeometric equation.
0
votes
1answer
26 views
A question in number theory based on asymptotics
I study number theory by myself and couldn't prove this question( Question number 12 , Chapter 13) Apostol Introduction to analytic number theory.
Let f(n) be a multiplicative function such that if p ...
0
votes
0answers
24 views
Question 13.11 on Apostol Introduction to analytic number theory
While self studying Number theory from Tom M Apostol Introduction To Analytic Number Theory I am struck on question 11 of chapter 13 on page 303.
For an arithmetic function f(n) prove that (a) ...
0
votes
0answers
28 views
Summation involving $O$-notation
I'm reading a proof where they conclude that
$$\sum_{k=1}^{\infty} \frac{O(\ln k)}{\epsilon^2\ln^2k} = \sum_{k=1}^{\infty}o_k(1) = \infty,$$
for a $\epsilon > 0$. Here the subscript $k$ means that ...
0
votes
0answers
14 views
Asymptotic sequence $\phi_{n,m}(\lambda)$
Consider a family of functions $$\phi_{nm}(\lambda) = \lambda^{m} e^{ān \lambda},$$ where the integers $n = 1, 2, 3, \cdot \cdot \cdot, \infty \ $ and $ \ m =1, 2, 3 , \cdot \cdot \cdot \ ,\ n.$
(a) ...
1
vote
1answer
27 views
Sequence asymptotically approaching multiplication by one constant if the previous term is odd and another if it is even
Say we have an integer sequence $G_k$, which in reality are the values of $$P(n)=5n^2+14n+1$$ for integers $n$ where $P(n)$ is a perfect square. Studying the values of this sequence, $$G_1=2\\
G_2=5\\...
3
votes
3answers
44 views
How close is $n $ to $ n \log n$?
How close is $n $ to $ n \log n$?
I know $\mathcal{O}(n) < \mathcal{O}(n \log n)$
But for some small $\epsilon > 0 , n^{1+\epsilon}=n \log n$. How much small is that $\epsilon$? The reason why i ...
1
vote
1answer
17 views
Understanding a bound on a group presentation length
If $G$ is a group, by a presentation of a group $G$, I mean a representation of $G$ by generators and relations.
If we have that the bound on a presentation length is $O({\left( {\log \;\left| G \...
4
votes
0answers
42 views
Is there a useful asymptotic expansion of $(1 + z^{\sqrt{2} - 1} + z^{\sqrt{2}})^{-1}$ at $z = 0$?
I believe that an asymptotic expansion in terms of powers of $z$ can not exist because we could use the geometric series to find something of the form
$$
\frac 1{1 + z^{\sqrt 2 - 1} +z^{\sqrt 2 }} = \...
1
vote
0answers
11 views
$O(x^y)$ and $O(x^{y+1})$, $O(C^y)$ and $O(C^{y+1})$
Let $x$, $y$ be variables and $C$ be a constant. How do these $O$
notations compare?
$O(x^y)$ vs $O(x^{y+1})$ (with $x^{y+1} = x * x^y$)
and
$O(C^y)$ vs $O(C^{y+1})$ (with $C^{y+1} = C * C^y)$
My ...
1
vote
1answer
21 views
Intuition behind $o(n)+\omega(n)+\Theta(n)=\Omega(n)$
Intuition behind $o(n)+\omega(n)+\Theta(n)=\Omega(n)$
Left hand side means set of all functions more than n + set of all functions greater than n + set of all functions equal to n ---> what does ...
0
votes
0answers
15 views
Intuition behind $f(n)+o(f(n)) = \Theta(f(n))$
Intuition behind $f(n)+o(f(n)) = \Theta(f(n))$
I could prove this using classical definations of o and theta. Also the proof is given in proof that a function plus a lower growth function is theta ...
2
votes
1answer
41 views
Laplace's method for integration
I am trying to compute $$I(\lambda) = \int_{0}^1 \frac{x}{\sqrt{1+x^4}}e^{\lambda x}\mathrm{d}x $$ for large, real, positive $\lambda$. I'm attempting this with Laplace's method as suggested, however ...
1
vote
1answer
48 views
Does there exist a Fourier series with such properties?
I am looking for a series $\sum_{n \in \mathbb{Z}}a_ne^{int}$ with the following properties :
$\bullet a_0=0$
$\bullet a_n=a_{-n} \geq 0$ for all $n$ in $\mathbb{Z}$
$\bullet \sum_{n \in \mathbb{Z}}...
2
votes
0answers
80 views
Asymptotics for 2 Humbert series special forms
I have 2 Humbert seriers special forms that arise in a quantum physics problem. $a$ and $x$ are real.
$$\phi_1(1+ia,ia,ia+3/2;1/2,ix)$$
$$\phi_2(ia,-ia,1/2;ix,-ix)$$
I want to find asymptotic ...
1
vote
1answer
63 views
Asymptotic behavior of $\int_{- \pi}^{\pi} \frac{\mathrm{d}\hat{m}}{2\pi} [e^{i \hat{m} m} \cos (\hat{m})]^N$
Given a real value $-1 \leq m \leq 1$, I need to determine the asymptotic $\left(~\mbox{large}\ N~\right)$ behavior of the following integral:
$$
\int_{- \pi}^{\pi} \frac{\mathrm{d}\hat{m}}{2\pi}\,
\...
0
votes
0answers
22 views
Find Stationary Points of Function in 4 complex variables
I have four contour integrals to evaluate around the origin for a function in the variables $z=(z_1,...,z_4)$. I want to evaluate such integrals by saddle point approximation, i.e. I need to find the ...
0
votes
2answers
26 views
Algorithm to find number of babysitters in $O(n)$ time
I want to hire a babysitter to watch over my baby 24 hours a day. I've gotten $n$ responses. Assume that all 24 hours can be covered. A babysitter is willing to work any part or parts of their ...
1
vote
1answer
25 views
Asymptotic expansion of integral of airy function
In this question I am given that the asymptotic expansion of the Airy function for large $z$ is given by
$$Ai(z) = \frac{1}{2}\pi^{-\frac{1}{2}}z^{-1/4}\exp\left(-\frac{2}{3}z^{\frac{3}{2}}\right)\...
2
votes
1answer
39 views
Prove that $\alpha^n<\sum_{k=1}^n {2n \choose n+k}k^2<\beta^n$, when $0<\alpha<4<\beta$ are constants
Let $\alpha,\beta$ constants such that $0<\alpha<4<\beta$. Prove that $\exists n_0.\forall n>n_0$ $$\alpha^n<\sum_{k=1}^n {2n \choose n+k}k^2<\beta^n$$
My attempt:
$$\sum_{k=1}^n {...
3
votes
1answer
30 views
Imaginary asymptotics for the digamma function
I often see asymptotics and precise expansion for the gamma $\Gamma$ or the digamma $\psi$ function $\psi$ when the argument goes to $+\infty$, in particular when it stays real (or in a given angle ...
0
votes
1answer
14 views
Is this order of the quantified variables correct for the definition of Big O?
So Big O says that for a function $f(x)$ to be in $O(g(x))$, then for some $C$, $k$, and all $x$, if $x > k$ then $f(x) \le Cg(x)$.
My question is whether this order of the quantified variables is ...
2
votes
0answers
33 views
Looking for a term for $f \in O(1/n^{1+\varepsilon})$
$\renewcommand\epsilon\varepsilon$ I'm interested to know whether there is any established expression for $f \in O(1/n^{1+\epsilon})$ for $n\to\infty$ for some $\epsilon>0$. Basically I'm looking ...
0
votes
0answers
29 views
Reference on least squares of nonlinear regression with product of coefficients
Consider OLS estimation of the model of the form $ \mathbf{y}=\mathbf{XB\delta}+\mathbf{u,}$ where $\mathbf{y}$ is a $N\times1$ vector of outcome, $\mathbf{X}$ is a
$N\times K$ matrix of data, $\...
0
votes
0answers
47 views
Asymptotic form of hypergeometric function ${}_1 F_1(a,b,z)$ at large $a,z$.
I am looking for the asymptotic form of the hypergeometric function ${}_1 F_1 (a,b,z)$
in the limit $a,z\rightarrow\infty$ with $a/z\rightarrow \mathrm{const}$, and $b\geq 1$.
Specifically, I am ...
0
votes
0answers
26 views
Big O notation for OEIS A015617
I am having difficulty finding the exact Big O notation for the size of the search space of OEIS A015617 as a function of n. I am researching a theory that A015617 may have useful applications in ...
1
vote
4answers
81 views
Find an asymptotic equivalent of the sequence $(\int_{-\infty}^{+\infty} \frac{1}{\cosh^n(x)} dx)_n$.
Find an asymptotic equivalent of the sequence $(\int_{-\infty}^{+\infty} \frac{1}{\cosh^n(x)} dx)_n$.
I found the result using a trick (using $e^x = \tan(\theta/2)$ as mentioned here) but I wanted to ...
0
votes
0answers
20 views
How to find the equations for a, b, c, d of the Master Theorem?
$$T(n)=a \cdot T\left(\frac{n}{b}\right)+\Theta\left(n^{c} \cdot \log ^{d} n\right)$$
Now I want to find equations for a,b,c,d
So a = ....
What I have tried to far is this:
$$T(n)=a \cdot T\left(\frac{...
0
votes
0answers
33 views
Is this formal definition of big O missing a quantifier?
I was reviewing the definition for Big O and came across this question. The following definition for whether a function is O(g(x)) was given:
f(x)=O(g(x))āā(āC,āk|C,kĻµRā§(x>kā|f(x)|ā¤C|g(x)|))
The OP ...
1
vote
1answer
32 views
Prove that $5 n \log_{2}(n) + 8 n -200 = \mathcal{O}(n \log_{2}(n))$
Ive been working on this problem for quite sometime now but cant seem to figure it out
This is what ive done so far:
$$5nlog_2(n)+8n-200 \le cnlog_2(n)$$
$$5+\frac{8}{log_2(n)}-\frac{200}{nlog_2(n)} \...
2
votes
3answers
59 views
Question about asymptotes.
Let $f(x) = 3\cdot\frac{x^4+x^3+x^2+1}{x^2+x-2}.$ Give a polynomial
$g(x)$ so that $f(x) + g(x)$ has a horizontal asymptote of $0$ as $x$
approaches positive infinity.
I've tried using that if the ...
1
vote
1answer
28 views
Watson's Lemma and Laplace transformation
Use Watson's lemma to find the expansion of $$F(\lambda) = \int_{0}^{\infty} e^{- \lambda t} sin(t)dt$$
,and verfify the answer using Laplace transformation by expanding the answer using Taylor's ...
2
votes
2answers
83 views
Asymptotic expansion of an integral as $x \to 0^{+}$
Find the asymptotic expansion of $$F(x) := \int_{x}^{1} \frac{1}{t \sqrt{1+t^2}} \ dt, \text{ as } x \to 0^{+}$$
I tried expanding $\frac{1}{ \sqrt{1+t^2}} = 1 - \frac{t^2}{2} + \frac{3 t^{4}}{8} + \...
1
vote
3answers
61 views
Prove that $\log(n!)=\Theta(n\log n)$ without appealing to Stirling's formula
Problem
Prove that $\log(n!)=\Theta(n\log n)$ without appealing to Stirling's formula.
Can somebody please verify my solution to this problem?
Solution
In this solution, I am going to use the ...
1
vote
1answer
49 views
Show that $\dfrac{(2n)!}{2^{2n}(n!)^2}$ is asymptotically equivalent to $\dfrac{1}{\sqrt{\pi n}}$
Problem
Show that $\dfrac{(2n)!}{2^{2n}(n!)^2}$ is asymptotically equivalent to $\dfrac{1}{\sqrt{\pi n}}$.
Can someone please verify my solution attempt?
Solution
Given functions $f(n)$ and $g(n)$, $...
1
vote
0answers
41 views
How to find the pattern in this data?
The unit covers Big-O notation. However, this may be irrelevant to the question.
This is the Professorās prompt:
For the following $T(n)$, find values of $n_0$ and $c$ such that $cn3$ is larger than $...
2
votes
0answers
28 views
Why is the $min\{r,f\} = O(r)$ = $O(r)$?
$min\{r,f\} = O(r)$
Can someone explain why this is true?
My current understanding is that $O(r)$ means an upper bound for $r$, so then anything asymptotically "smaller" than $r$ would fall ...
1
vote
1answer
27 views
transition between 1+o(1) notation to little o and omega problem
I need to find $a\in\mathbb{N}$ so that ${3n-1 \choose 2n} = \omega(a^n)$ and ${3n-1 \choose 2n} = o((a+1)^n)$.
First, I showed that ${3n-1 \choose 2n} = \frac{1}{3} {3n \choose n}$.
I then used ...
1
vote
2answers
39 views
Disprove $(2^n)^{\frac{1}{3}} \in \theta(2^n)$
I know we can prove this simply by saying we can't find such $c_1,c_2$ but the question asks me to prove this by proving its negation is true. (the hint of the problem says this will be hard)
We ...
2
votes
0answers
69 views
How to evaluate $\lim_{{n}\to\infty}{\sum_{{k}\leq{n}}{\left\lvert\frac{\sin{k}}{\ln{n^k}}\right\rvert}}$?
Show that $$\sum_{k=1}^n{\mspace{-2mu}\frac{\left\lvert\sin{k}\right\rvert}{k}}\sim\frac{2}{\pi}\mspace{-1.5mu}\sum_{k=1}^n{\mspace{-2mu}\frac{1}{\mspace{-1mu}k}}$$ as $n\to\infty$.
Alternatively, ...
0
votes
0answers
15 views
What is the dominant balance for this system of ODEs
Consider the following system on $t\in(0,\,\infty)$:
$$A'(t) = -A^2(t)-0.5B^2(t) $$
$$ B'(t) = -1.5A(t)B(t).$$
I know from numerical simulations of this model that the correct dominant balance for ...
1
vote
0answers
56 views
What does “$\prec$” mean, as in $g(x)\prec e^{-x^2/2}$?
I just had a question regarding mathematical notation. I have never seen this "$\prec$" symbol before. Does it just mean $g(x)$ is less than the function?
Thank you!
1
vote
0answers
54 views
Asymptotic expansion of the solution of a Heat Equation
Given $g$ is differentiable function such that $g(0)=0$.
Prove that an asymptotic expansion of an integral: $$u(x,t) = \frac{x}{2 \sqrt{\pi}} \int_{0}^{t} \frac{e^{-x^2/4\tau}}{\tau^{3/2}} g(t-\tau) \ ...
0
votes
1answer
15 views
Asymptotics of the Fourier transform of a non-analytic function involving an exponential
While reading this article, the I was puzzled by the following statement, used several times in the article. Consider a function $f(x)$ whose Fourier transform is
$$
\hat{f}(k) = \exp\left(-c {|k|^\...
0
votes
0answers
29 views
Finding a lower bound for a sinc sum
I am interested in developing an accurate estimate for the following function:
$$
F(A) = \frac{1}{2}+ \frac{1}{\pi}\sum_{t=1}^{\infty}\frac{\sin(A t)}{t},
$$where $A$ is a real number, in fact a ...
2
votes
1answer
29 views
Prove that if 𝑓(𝑛) = Ī(𝑔(𝑛)), then ln(𝑓(𝑛)) = Ī(ln(𝑔(𝑛))) [closed]
Let š(š) and š(š) be asymptotically positive functions, and assume that lim šāā š(š) = ā. Prove that if š(š) = Ī(š(š)), then ln(š(š)) = Ī(ln(š(š)))
