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

learn more… | top users | synonyms (1)

13
votes
2answers
429 views

Laplace's method

I'm still having a little trouble applying Laplace's method to find the leading asymptotic behavior of an integral. Could someone help me understand this? How about with an example, like: ...
0
votes
2answers
131 views

Asymptotic integral expansion of $\int_{0}^{\pi/4}{d\theta \over \epsilon^2+\sin^2\theta}$ for $\epsilon \to 0$

I am studying how to evaluate the integral $$\int_{0}^{\pi/4}{d\theta \over \epsilon^2+\sin^2\theta}$$ as $\epsilon \rightarrow 0$ with asymptotic methods. The book perturbation methods by Hinch ...
3
votes
1answer
96 views

Integral asymptotic expansion of $\int_0^{\pi/2} \exp(-xt^3\cos t)dt$ as $x \to \infty$

I have the integral $$I(x)=\int_0^{\pi/2}\exp(-xt^3\cos t)dt$$ and I want to derive the first two terms in the asymptotic expansion for $x\rightarrow \infty$, which should give me ...
5
votes
1answer
166 views

Integral asymptotic expansion of $\int_{0}^{\infty} \frac{e^{-x \cosh t}}{\sqrt{\sinh t}}dt$ for $x \to \infty$

$$\int_{0}^{\infty} \frac{e^{-x \cosh t}}{\sqrt{\sinh t}}dt$$ I'm trying to use Laplace's method to find the leading asymptotic behavior as $x$ goes to positive infinity, but I'm having some trouble. ...
1
vote
0answers
78 views

Find the Laplace approximation of $\frac{1}{2\pi} \int_{-\pi}^{\pi }e^{x\cos(\theta )}d \theta$ for $ x \to \infty$

Let's have integral $$ I(x) = \frac{1}{2\pi} \int \limits_{-\pi}^{\pi}e^{x\cos(\theta )}d \theta, \quad x \to +\infty . $$ How to use Laplace approximation for this integral and find first two ...
1
vote
3answers
48 views

How to evaluate this exponential fraction limit?

I am trying to determine if 3$^n$ grows faster than 2$^{2n}$. One way I found online to do this was, from Growth was to evaluate $\lim_{n\to \infty} \frac{3^n}{2^{2n}}$ and if that limit evaluates ...
0
votes
1answer
19 views

Prove that $\frac{f(n)+a}{g(n)+b} = O(\frac{f(n)}{g(n)})$

I was reading about algorithm analysis and I saw a similar simplification done in order to find the complexity. I became interested in proving that this simplification is formally correct but I am ...
1
vote
1answer
19 views

If $x$ is a $\chi^2_{N-n}$ RV. what is $x/N$ as N goes to infinity

We know that if we have $N-n$ gaussian iid RVs $\{e_i\}$ with mean $0$ and variance $1$, the RV $x = \sum e_i^2$ is $\chi^2$ distributed with $N-n$ degrees of freedom. We have $N$ larger than $n$. I ...
1
vote
1answer
17 views

A question regarding the order of an asymptotic estimate

Suppose that $m, n \in \mathbb{N}$ such that \begin{equation} m \cdot \log m = n, \end{equation} where the logarithm is in the natural base. How can we estimate the solution $m = m(n)$ ...
2
votes
1answer
84 views

What does the sign “$=$” exact meanings?

How can I understand the sign "$=$" from the following expression: $$\mathcal{o}f((x))=\mathcal{o}f((x))+\mathcal{o}f((x));$$ $$\mathcal{o}(kf((x)))=\mathcal{o}(f(x));$$ ...
0
votes
0answers
8 views

How would I compare these differential statements using Big O notation?

I am doing an econ problem. The question asks me to basically discuss in economic terms the effect of increasing or decreasing $\alpha$ on the function $$1= x^\alpha y^{1-\alpha}$$ Anyways, I've ...
1
vote
0answers
36 views

Asymptotic of $\int_0^x \int_x^{2\pi} \sin^2(N(u-v)/2)/\sin^2((u-v)/2)\,du\,dv$ [closed]

How can I prove $$ \int_0^x \int_x^{2\pi} \frac{\sin^2\Bigl(N(u-v)/2\Bigr)}{\sin^2\Bigl((u-v)/2\Bigr)}\,du\,dv \sim \pi^{-2} \log N $$ as $N \to \infty$? I am told the asymptotic does not depend on ...
0
votes
2answers
34 views

Asymptotic Algorithm General Approach to Finding $\Theta$ Bound

I'm working on the following asymptotic algorithm bounds problem Find a $\Theta$ bound for $f(n) = \frac{n^2}{2} - \frac{n}{2}$ So I could find the big-$O$ bound fairly easily $$ 0 \leq ...
0
votes
1answer
25 views

Floor function and little oh notation

Can we replace $o([x]^a)$ where $[x]$ is floor of $x$ and $a$ is a positive number with $o(x^{a})$? And can we replace $o(x^{a})$ with $o([x]^a)$?
0
votes
1answer
41 views

Confusion on Big $O$

I am so confused on the intuitive idea behind Big $O$ notation. $f(x)=O(g(x))$ iff there is a constant $C>0$ such that for large $x, |f(x)|\leq C|g(x)|$ and I have seen that in many places that ...
1
vote
1answer
30 views

How to show $n \sum_{k>n} (k^2 \log k)^{-1} \sim (\log n)^{-1}$?

How does one show that $$n \sum_{k>n} \frac{1}{k^2 \log k} \sim \frac{1}{\log n} \quad ?$$ Many thanks for your help.
1
vote
2answers
62 views

Number of distinct prime divisors of an integer $n$ is $O(\log n/\log\log n)$

I strongly believe that the claim is true; but I'm neither a mathematician nor speaking French and hope that somebody can confirm it, since related questions (here, here and here) either don't have an ...
0
votes
0answers
14 views

Approximate distribution of product of N normal i.i.d.?

Given $N>30$ i.i.d. $X\approx\mathcal{N}(\mu_X,\sigma_X^2)$, looking for: accurate closed form distribution approximation of $Y=\prod_{n=1}^{N}{X}$ asymptotic normal approximation of same ...
1
vote
1answer
52 views

Which way is best to solve: $T(n)=5T(n/5) + n\;?$

I'm not sure which way is best to solve $$T(n)=5T(n/5) + n$$ (recursion tree/master method/recurrence?) I would like some assistance, which way is easier and how can I be sure I got the right answer ...
2
votes
0answers
23 views

Biggest rate of growth of a sequence in $ℓ^2$

$ℓ^2$ is the space of complex sequences $u_n$ such that $\sum |u_n|^2$ converges. I'm wondering if there are asymptotic results known about such sequences. We have trivially $u_n=o(1)$. Are better ...
1
vote
0answers
34 views

If I colour $n$ vertices independently, randomly with $n^{(1-x)}$ colours, why is the size of the colour classes $(1+o(1))n^x$?

By $o(1)$, I mean 'little-o' of $1$. A paper I'm reading uses this result, but I can't see where it comes from. Thanks.
1
vote
1answer
20 views

Is this statement correct $f(n) = \theta(n) \land g(n) = \Omega(n) \Longrightarrow f(n)g(n) = \Omega(n^2)$?

I am having some difficulties understanding what does it mean to "and" $\theta(n)$ and a function $g(n)$, what does it mean in mathematical terms? Specifically, in the following example, I have to ...
0
votes
0answers
16 views

Show T(n)=T(n/5)+T(4n/5)+n/2 is $\Omega (n log n)$

I'm tasked with showing T(n)=T(n/5)+T(4n/5)+n/2 is Big-Omega n log n by drawing a recursion tree. The tree shows a lower bound with the following terms: n/2 ... n/10 ... n/50 ... etc. When I solve ...
1
vote
1answer
30 views

Asymptotic behavior of the confluent hypergeometric function

Consider the following function $$U(a,z)= \frac{1}{\Gamma(a)} \int^{\infty}_0 t^{a-1} \cdot (1+t)^{-a} e^{-zt} dt$$ My Try : Let $\tau= zt$, then : $$ U(a,z)= \frac{z^{-a}}{\Gamma(a)} \int^{\infty}_0 ...
0
votes
1answer
50 views

How rapidly does $\Gamma(x)$ diverge as $x$ approaches $0$?

Notoriously $$\lim\limits_{x\to0^{\pm}}\Gamma(x)=\pm\infty,$$ but can we be more precise (tightly) bounding from above $\left\lvert \Gamma(x) \right\rvert$ when $x$ is close to $0$? I could not find ...
4
votes
2answers
86 views

Laplace's method with nontrivial parameter dependency

I need to approximate the following integral using Laplace's method: $$ \int_0^{\infty} \frac{x^{\lambda} \lambda^{-x}}{(1+x^2)^\lambda} dx \\ = \int_0^{\infty} \exp\left(\lambda \log(x) - ...
0
votes
1answer
18 views

Asymptotic-Proof

I am looking at this questions and the proof for it and wondering how this works.Can anyone explain the answer to me or do you have any other way to answer this question.I am new to asymptotic ...
5
votes
1answer
58 views

Why does Titchmarsh say that we can move the derivative under $\frac{2}{\pi}\int_0^\infty \frac{\Xi(t)}{t^2 + \frac{1}{4}} \cosh(\alpha t) \, dt$

If we define the Riemann-Xi function as $$ \Xi(t) = \xi(\frac{1}{2} + it)$$ where $$\xi(s) = \frac{1}{2}s(s-1)\pi^{-\frac{s}{2}}\Gamma(\frac{s}{2})\zeta(s),$$ then according to Titchmarsh in his ...
1
vote
1answer
19 views

limiting variances of iid sample mean

In the book Statistical Inference (George Casella 2nd ed.), page 470, there is an example: $\bar{X}_n$ is the mean of $n$ iid observations, and E$X=\mu$, $\operatorname{Var}X=\sigma^2$. "If we take ...
1
vote
1answer
71 views

Is it possible to find the least common divisor of a two numbers that are not relatively prime in polynomial time?

As the question states: Is it possible to find the least common divisor of two number that are not relatively prime in polynomial time? If so, how? Thanks!
3
votes
0answers
33 views

Merten's function

I am tasked with applying the Wiener-Ikehara Theorem to achieve a bound of little o(x) on Merten's function $\sum_{n=1}^x \mu (n)$. My problem is the Wiener-Ikehara Theorem applies to Dirichlet series ...
0
votes
2answers
30 views
1
vote
0answers
36 views

Asymptotic Proof

Can someone explain this asymptotic proof to me.I am stuck at the inductive step and get lost around this step $2 × n! < (n + 1) × n!$ $$2n = o(n!)$$ True Proof: In order to $2n = o(n!)$ be true, ...
2
votes
1answer
55 views

How to find $s(\exp(d(x)))$ ~ $ x + 2 $?

Let $x$ be a positive real. I want to find a pair of analytic functions $s(x),d(x)$ such that $s(d(x)) = x$ and $ s(\exp(d(x)))$ ~ $ x + 2 $ More presicely I Also want : $$ \lim_{x \to \infty} ...
2
votes
2answers
19 views

Find the minimum value of $n$ such that $\sin^n(c)<\varepsilon$ for some small constant $\varepsilon>0$

Let $c$ be a constant such that $0 <c \le \pi/2$ and $\sin(c) \ne 0$. Question: What is the minimum value of $n$ such that $\sin^n(c)< \varepsilon$ for some small constant $\varepsilon >0$ ? ...
0
votes
0answers
22 views

What should be the optimal order of $x$?

Let $f(x,y) = O\left(y^{-1}x^a\exp(x^b) + x^{c}\right)$. I would like to find the optimal order of $x = x(y)$ such that $f(x,y)$ is minimized as $y\to\infty$. The problem I have is due to the ...
0
votes
1answer
21 views

asymptotic complexity of functions

I'm curious if my asymptotic analysis of these functions are correct. I know the process is to strip the constants and then get to where its just comparing functions and taking limit to infinite and ...
3
votes
2answers
88 views

Asymptotic Behaviour Of $\frac{1}{x-1}+\frac{1}{x^2-1}+\frac{1}{x^3-1} + \cdots$ as $x \to 1 $

I define $$ f(x) = \sum_{n=1}^{\infty} \frac{1}{x^n-1} = \frac{1}{x-1} + \frac{1}{x^2-1} + \frac{1}{x^3-1} +\frac{1}{x^4-1} + \frac{1}{x^5-1} + \cdots$$ and I then wish to study the asymptotic ...
0
votes
1answer
28 views

Design an algorithm - Median, computer science

I was wondering if this question belongs here or on StackOverflow, but it is a question of mathematical nature so this seems more appropriate. We have an array $S$ of $n$ different numbers ...
6
votes
2answers
36 views

If $f(n)$ is $O(g(n))$ and $g(n)$ is $O(f(n))$, is $f(n) = g(n)$?

Question: If $f(n)$ is $O(g(n))$ and $g(n)$ is $O(f(n))$, is $f(n) = g(n)$? I'm studying for a discrete mathematics test, and I'm not sure if this is true or false. Since Big-OH ignores constant ...
1
vote
1answer
40 views

Asymptotic behavior of the zeros of the digamma function

The gamma function has just one extremum on each interval $(k,k+1)$, where $k$ is a negative integer. These extrema occur at the zeros of the derivative of the gamma function. Let $z_n$ denote the ...
1
vote
0answers
30 views

Summation involving digamma and floor functions

I am trying to find an asymptotic expansion for the following sum: $$\sum_{n=1}^K \frac{\phi_0( 1/2+n+\lfloor(2n-1)/\sqrt{2}\rfloor)}{(4n-2)}$$ where $\phi_0$ is the digamma function and $\lfloor ...
2
votes
0answers
25 views

Asymptotic solution to $m \leqslant e^{\lambda t} (c t^q - \varepsilon)$

What is the smallest $t$ statisfying the inequality: $m \leqslant e^{\lambda t} (c t^q - \varepsilon)$, where $\varepsilon$ is arbitrary small positive number? I believe $t$ must be of the from: $$t = ...
2
votes
0answers
38 views

Asymptotic behavior of $1/(a^2+\epsilon^2)$ as $\epsilon\to0$

A limit that often arises in physics is $$ \lim_{\epsilon \to 0} \frac{ \epsilon }{ a^2 + \epsilon^2 } = \pi \delta(a) ............ (1) $$ Is there a similar sort of limit for $$ \lim_{\epsilon \to 0} ...
0
votes
0answers
22 views

Asymptotic analysis of $\int_{0}^{\infty} \frac{\sqrt k J^2_{\ell}(k) \sin{(\tau\sqrt k)}}{(k+1/2)^{n+2}} dk$

Question as the title showed, in which $n$ and $\ell$ are positive integers, $\tau$ is real number and $J$ means Bessel functions. How to do the asymptotic analysis when $\tau$ approaches zero? Any ...
2
votes
1answer
30 views

Simple vs compound interest rates and Taylor expansion

I am having trouble deciphering a portion from my finance text. Let $i = \text{interest rate}$, $n = \text{Some arbitrary time period}$ and $C = \text{Cash invested}$ And also $C(1+i)^n$ ...
6
votes
3answers
154 views

Aproximation of $a_n$ where $a_{n+1}=a_n+\sqrt {a_n}$

Let $a_1=2$ and we define $a_{n+1}=a_n+\sqrt {a_n},n\geq 1$. Is it possible to get a good aproximation of the $n$th term $a_n$? The first terms are $2,2+\sqrt{2}$, $2+\sqrt{2}+\sqrt{2+\sqrt{2}}$ ... ...
3
votes
1answer
40 views

Prove that $3\log n$ is $O(\exp(0.001n))$

First time posting here. Hi math stack-exchange community! I have a bonus question on my assignment and I am having trouble proving it. The main reason is that I am only limited to using the rules ...
3
votes
3answers
41 views

Rule for calculating big-O plus example I can't figure out

I have the following rule: If $f$ is $O(g)$ for ${x\to\infty}$ and $\lim_{x\to\infty}g(x) = 0$ than also $\lim_{x\to\infty}f(x) = 0$ Then my text proceeds to give an example: ...