Questions tagged [asymptotics]

Questions involving asymptotic analysis, including growth of functions, Big-$O$ notation, Big-$\Omega$ and Big-$\Theta$ notations.

Filter by
Sorted by
Tagged with
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(𝑔(𝑛)))

1
2 3 4 5
147