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

learn more… | top users | synonyms (1)

3
votes
0answers
52 views

Need help bounding Merten's function for large x

Recall that Merten's function is defined as: $$M(x) = \sum_{n\le x}\mu(n)$$ Using the following prime counting functions to represent the count of integers less than $x$ with $k$ prime divisors: $$\...
1
vote
1answer
97 views

Show $R(x)=o(x^3)$

I got $$R(x)=4! \, x^4 \int _0^{\infty} \frac{1}{(1+xt)^{5}}e^{-t} \, \, dt$$ is this correct? I have no idea what to do for the last part of ii
1
vote
0answers
14 views

Proving three asymptotic identities (Murray (1984)'s Exercise 1.1.4)

(Context: I'm self-studying Murray (1984). I learned (and have forgotten quite a lot of) real and complex analysis. I'm willing to relearn and to look up references.) Problem: if $f=O(g)$, show that ...
0
votes
0answers
16 views

Method of stationary phase when the stationary point is neither minimum nor maximum.

I am trying to evaluate the leading order behaviour of $I(x) = \int_{0}^{1} e^{ix(t-sin(t))} dt$, using the method of stationary phase. The way we have been taught to solve these types of integrals is ...
1
vote
1answer
25 views

How to know which boundary condition to use

With asymptotic methods for ODEs where you have like an inner, outer region and you are given two boundary condition, how do you know which condition to use when constructing the inner/outer solution? ...
0
votes
2answers
31 views

Solving an asymptotic equation

Suppose for $t$ in some neighborhood $(0,\delta)$, we define $s>0$ via $$ \frac{a_2}{2!}t^2+\frac{a_3}{3!}t^3+\cdots=-s^2 $$ where $\{a_2,a_3,\ldots\}$ is such that $a_2<0$ and the LHS above ...
1
vote
0answers
45 views

asymptotic behavior of functions which are defined recursively

For $x\in[0,1]$, define $f_1(x)=1$ and $$ f_{n+1}(x)=(1-x)^n\left(nx+1\right)+f_n(x)\left(1-(1-x)^{n+1}\right)\;\;\mbox{for}\;\;n=1,2,\dots. $$ I want to study some asymptotic results of $f_n$. For ...
2
votes
0answers
30 views

Can anyone give an example of a set of numbers with arithmetic density that doesn't converge to a limit?

Question in the title. All of the examples I can think of (congruence classes, primes, etc.) converge as n goes to infinity.
0
votes
1answer
35 views

Dominant Balance with epsilon small

Consider the boundary value problem $$ε \frac{d^2y}{ dx^2} + (1 + x) \frac{dy }{dx} + y = 0$$ subject to $y(0) = 0$, $y(1) = 1$, for $0 \le x \le 1$, $ε ≪ 1$. By considering the rescaling $x = x_0 + ...
0
votes
1answer
18 views

Determine asymptotic complexity of the code

I need to determine asymptotic complexive. ...
1
vote
1answer
31 views

How to solve master theorem $T(n) = 3T\left(\frac{n}{2}\right) + \frac{n^2}{\log_2 n}$

Im trying to solve this using master theorem $T(n) = 3T\left(\frac{n}{2}\right) + \frac{n^2}{\log_2 n}$ but I dont know how. So far we know that $a=3$, $b=2$, $f(n) = \frac{n^2}{\log_2 n}$. Which ...
2
votes
2answers
55 views

$\ln(x)$ and Big O notation

I have tried to assert that $\ln(x)=O(x^0)$ a few times, but it seems fairly obvious that this statement should be false, and so I've been faced with some rightful speculation. My reason is that $$\...
0
votes
0answers
18 views

Extension of Coupon Collector Problem with at least $k$ items per coupon [duplicate]

In the standard coupon collector problem we have an urn with $n$ different coupons, from which coupons are being collected, equally likely, with replacement. Simple analysis shows that the expected ...
3
votes
3answers
39 views

Showing that $\log(n)^{\log(\log(n))} \in \mathcal{O}(n)$

I want to show that $$\log(n)^{\log(\log(n))} \in \mathcal{O}(n)$$ where $n \in \mathbb{N}_{≥2}$, and $\mathcal{O}$ is the big-O-notation. It seems like a relatively simply statement, but so far, ...
0
votes
1answer
29 views

Why is $lg(\theta(\frac{1}{n}))$ = $\theta(\frac{1}{n})$?

I'm trying to follow a proof of an exercise from an algorithms textbook, and am confused about one the algebraic steps in the proof: $lg(\theta(\frac{1}{n}))$ = $\theta(\frac{1}{n})$ Where $lg$ is $...
0
votes
1answer
27 views

Asymptotic behaviours from Fourier transforms

I have completely forgotten how one derives the asymptotic behavior in frequency space, given the asymptotic behavior of the function in real space (e.g. time). As an example example, it is often said ...
4
votes
2answers
58 views

Why does the Number of Graphs on $n$ Vertices Blow up so Quickly?

See for example here: https://en.wikipedia.org/wiki/Graph_enumeration I would have thought (naively) that the number of graphs on $n$ vertices would only grow as $\mathscr{O}\left( _nC_2\right)$, but ...
1
vote
0answers
24 views

A question on Edgeworth Expansion

I'm working Edgeworth Expansion. I couldn't understand one thing . Can you help me about that please. $$Z= \frac{\sqrt {n} (\bar {x} -\mu)}{\sigma}$$ converges in distribution to N(0,1) I have ...
2
votes
2answers
78 views

Asymptotic for combinatorial function

Let $$F_q(k) = \sum_{n=1}^{\infty} \binom{n-1}{k} \binom{1/2}{n} q^n$$ be a function on $\mathbb{N}$. I am interested in the asymptotic behavior of $F$. Any ideas how to tackle it?
1
vote
0answers
38 views

Leading Order $\epsilon \frac{\mathrm{d}^2y }{\mathrm{d} x^2} + 12x^{\frac{1}{3} }\frac{\mathrm{d} y}{\mathrm{d} x}+y= 0 $

I am required to find the leading order outer and inner solutions and then the constants by asymptotic matching. I have shown there exists a boundary layer at x=0 and hence have use the condition$ y(...
0
votes
0answers
33 views

What is the fundamental difference between matched asymptotic expansion and multiple scale analysis?

I was wondering about the fundamental difference between the matched asymptotic expansion and the method of multiple scales. They both work extremely well for singularly perturbed problems. Do they ...
1
vote
3answers
38 views

Approximation of an indefinite integral

Consider this integral $$\frac{1}{2d}\int_{-d}^{d}f(x-t) \, \mathrm{d}t$$ When $d$ goes to zero, $$\lim _{d\to 0} \frac{1}{2d}\int_{-d}^{d}f(x-t) \, \mathrm{d}t = f(x)$$ but what is the second ...
6
votes
4answers
213 views

Limit of $\sqrt{\frac{\pi}{1-x}}-\sum\limits_{k=1}^\infty\frac{x^k}{\sqrt{k}}$ when $x\to 1^-$?

I am trying to understand if $$\sqrt{\frac{2\pi}{1-x}}-\sum\limits_{k=1}^\infty\frac{x^k}{\sqrt{k}}$$ is convergent for $x\to 1^-$. Any help? Update: Given the insightful comments below, it is ...
0
votes
1answer
20 views

Do lower order terms matter in Big Omega

Consider the function $(n-1)^2.$ Clearly this is $\mathcal{O}(n^2)$ since the constant for the upper bound is $1.$ However, it seems to me that it is not $\Omega (n^2)$ since this is a strictly ...
1
vote
1answer
21 views

Big-O of Set of Functions

I'm a bit puzzled on how to understand a bound. We have two functions $f$ and $g$ such that $$ f(n) = n^2 - n + 2 $$ and $$ g(n) = 4n^2 +3n +2 $$ If we try to see if $f = O(g)$, we use the limit ...
0
votes
2answers
56 views

Comparison between $n\log n$ and $n^2$ sorting algorithms

Suppose we have two sorting algorithms which takes $O(n\log n)$ and $O(n^2)$ time. What can we say about it? Is it always better to choose $n\log n$ if the size $n$ is not given? Or can we say on an ...
0
votes
0answers
12 views

General procedure for solving 'asymptotic equation'

I have an equation of the form $f(n) \sim g(f(n)) \quad (n \uparrow \infty)$ where the function $g$ is known and I want to find an $f $ satisfying it. (The solution of course will not be unique in ...
0
votes
0answers
32 views

On random subset combinatorics.

Suppose we have $2^n$ elements in a set. We have $cn^\beta$ random subsets of cardinality $\frac{2^n}{c}$ elements each where $c,\beta>1$ holds. Fix a random subset of $n^\alpha$ elements $A$ ...
0
votes
1answer
23 views

Determine if the function is $O(x^2)$ . If so find the constants $C$ and $k$ to verify.

Determine if $ f(x) = 4x^2+x+1$ is $O(x^2)$. If so find the constants $C$ and $k$ to verify that the function is $O(x^2)$ My solution is: \begin{align} & |f(x)| \le C|x^2| \ \ \ \ \ \ \forall x ...
1
vote
1answer
34 views

How to expand $x^n$ as $n \to 0$?

I am trying to expand $x^n$ in small $n$ using Taylor series. Using wolfram alpha, I found that it is $1+ n\log(x) + \cdots$ I tried to Taylor expand $x^n$ around $n=0$ but I cannot get this result.
0
votes
0answers
18 views

Asymptotic expansion of $\sum_{n\le x}\log^2n$ [duplicate]

The following formula is used without proof in a step in the Prime Number theorem, from Shapiro "Introduction to the Theory of Numbers": $$\sum_{n\le x}\log^2n=x\log^2x+b_1x\log x+b_2x+O(\log^2x)$$...
0
votes
0answers
11 views

Can you use Dirichlet's hyperbola method with any of these pathological logarithms?

I would like to learn Dirichlet's hyperbola method in some of myself next posts. I know its meaning and relationship with the divisor function and lattice problems, but in this ocassion I want to ...
2
votes
1answer
55 views

How do we know which terms are of higher order?

From Asymptotic analysis and perturbation theory by Paulsen: Find the behavior of the function defined implicitly by $$x^2+xy-y^3=0$$ as $x\to\infty$. [...] At this point, we have shown ...
2
votes
1answer
38 views

When is a balance assumption consistent?

From Asymptotic analysis and perturbation theory by Paulsen: Find the behavior of the function defined implicitly by $$x^2+xy-y^3=0$$ as $x\to\infty$. [...] The final case to try is to ...
1
vote
1answer
34 views

Asymptotic analysis references

I'm self studying asymptotic analysis with Bruijn (1981) - Asymptotic Methods in Analysis Bleistein and Handelsman (1986) - Asymptotic Expansions of Integrals but the texts are terse, without too ...
0
votes
0answers
32 views

Asymptotics of a mean of exponential terms involving Gaussians

Let $X\sim \mathcal{N}(0,I_p)$ and $\tau=\sqrt{(2-\varepsilon)\log p}$ and $\varepsilon>0$. I want to prove that for sufficiently small $\varepsilon>0$ the following holds: $$ \mathbb{E}\left[ \...
0
votes
1answer
14 views

Big O of a difference

Assume $f,g$ are such that $$\lim\limits_{n\to\infty}\frac{f(n)}{g(n)}=r\in\mathbb{R}.$$ Is there anything non-trivial we can infer about $$\left|\frac{f}{g}-r\right|$$ in terms of big-O notation, ...
1
vote
0answers
17 views

Trying to find the asymptotic behaviour of an inequality involving integers

Let $m,q,v$ be integers with $m\geq 2$, and $v|q-1$. A certain result that I have which is not important for this question, holds when $$q^{\frac{m}{2}-2}(q-mv)\geq v^{m-1}. \quad (1)$$ I would like ...
2
votes
1answer
88 views

Why is $\varepsilon x^5 \sim -x$?

I'm trying to understand what's going on in this lecture on perturbation (the link brings you to 1h 08m 12s). The original problem is to find the real root of $$x^5+x=1.$$ We have inserted $\...
3
votes
0answers
64 views

What's about $\sum_{n=1}^{\infty} \frac{e^{H_n}\log H_n}{n^3}$, where $H_n$ is the nth harmonic number?

I would like to do a toy verification of the Riemann hypothesis exploiting theLagarias theorem (see the section Applications in the following link) and the fact that we know a lot of decimals for ...
4
votes
0answers
91 views

A conjectured asymptotic expansion of a function related to the sine and cosine integrals

Recall the definitions of the sine and cosine integrals:$$\operatorname{Si}(x)=\int_0^x\frac{\sin t}t dt,\quad\operatorname{si}(x)=-\int_x^\infty\frac{\sin t}t dt=\operatorname{Si}(x)-\frac\pi2,\tag1$$...
3
votes
2answers
47 views

Minimize a particular function in one variable

For given $a,b$, what is the minimum value of the following expression? $$ \frac{a}{x^2+b}+x,\qquad x>=0, a>0,b>0 $$ Differentiating the above gives a messy polynomial. I tried plugging ...
4
votes
1answer
67 views

My attempt to follow Tatuzawa and Iseki strategy to get a bound for $\int_2^x \frac{dt}{\log t}-\pi(x)$, where $\pi(x)$ is the prime counting function

I don't know if this exercise is in the literature, where $Li(x)=\int_2^x\frac{dt}{\log t}$ is the logarithmic integral and $\pi(x)$ is the prime counting function Question. Compute a good bound ...
4
votes
1answer
42 views

Proving recurrence relation with induction: $T(n) = T(n-1) + n$

I have to prove that the bound of the following relation is $\theta(n^2)$ by induction- $$T(n) = T(n-1) + n$$ should i seprate my induction into two sections - to claim that $T(n) = O(n^2)$ and $...
0
votes
2answers
40 views

Can we Relate Radius of Convergence of Taylor Series and Asymptotic Rate of Growth?

I still need to be disabused of the belief that there is some simple connection between the finiteness of the radius of convergence and the asymptotic rate of growth. 1. Can we develop any ...
1
vote
1answer
21 views

Is Every (Real) Analytic Function (with Non-Degenerate MacLaurin Series) Asymptotically Greater Than any Polynomial?

Question: Given a function $f: \mathbb{R} \to \mathbb{R}$ such that the MacLaurin series exists and equals the function for every $x \in \mathbb{R}$, and such that for all $n \ge n_0$, $n_0$ some ...
1
vote
2answers
32 views

Is it true that $ \sum_{i=1}^m \frac{1}{\sqrt{i}} = O \left( \sqrt{ m-1 } \right) $?

Is it true that?: $$ \sum_{i=n}^m \frac{1}{\sqrt{i}} = O \left( \sqrt{ \frac{m-n}{n}} \right) $$ In special case if we have $n = 1$, is it true that?: $$ \sum_{i=1}^m \frac{1}{\sqrt{i}} = O \left( \...
0
votes
1answer
65 views

Upper bound on $(1 + x)^n$

I'm looking for a useful upper bound on $(1 + x)^n$ in terms of $n$ and $x$. You can assume $x > 0$. Does anyone know one? An asymptotic upper bound would also be helpful.
1
vote
0answers
38 views

Upper-bounding $\sum_{i=1}^n \sum_{j = i}^{i+a_i} \frac{1}{\sqrt{j}}$?

Suppose $a_1, ..., a_n \in \mathbb{N}$ are arbitrary integers. Is it possible to bound $$ A =\sum_{i=1}^n \sum_{j = i}^{i+a_i} \frac{1}{\sqrt{j}} $$ with either of the following: $$ B = c\sqrt{\sum_{...
1
vote
2answers
94 views

Show $\sum_{n\le x}\frac1{\sqrt n}=2\sqrt x+c+O(x^{-1/2})$

I am trying to show the asymptotic expansion for $$\sum_{n\le x}\frac1{\sqrt n}=2\sqrt x+\zeta(1/2)+O(x^{-1/2}).$$ (The exact identity of the zeta term is not important, it need only be some $c$.) To ...