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

learn more… | top users | synonyms (1)

-1
votes
2answers
39 views

Asymptotics of $\sum_{n}e^{-n^{2}}$.

Define the function $S(N)$ as $$S(N)=\sum_{n=0}^{N}e^{-n^{2}}$$ I am interested in the asymptotic behavior of $S(N)$ for large $N$. It is clear by the ratio test that $\lim_{N\rightarrow\infty}S(N)$ ...
1
vote
0answers
26 views

Non-trivial inverse Laplace transform

I'm trying to compute the inverse Laplace transform of $f(s) = s^c/(N + s^{ir} )$ where $c,N \in \mathbb{C}$ and $r \in \mathbb{R}^+$ using the Bromwich integral $$ F(t) = \frac{1}{2 \pi i} \int_{- ...
1
vote
1answer
13 views

As $x \to 0$ this approaches zero since the zero of $e^{\frac{-1}{x^2}}$ beats out the pole of $\frac{1}{Q_k(x)}$?

In the Robert Strichartz's book "A Guide to Distribution Theory and Fourier Transforms" at the page $4$, we have an interesting exercise : $$ \psi(x) = \begin{cases} e^{\frac{-1}{x^2}} ...
0
votes
1answer
18 views

Find the inner solution

I need to show that the leading order inner solution is given by the below. Thus far, I have rescaled and showed the boundary layer is of order $\epsilon^{\frac{3}{4}}$. Hence at leading order I ...
1
vote
1answer
87 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
votes
0answers
19 views

How to show a function is $<<$ to an integral [on hold]

For those integrals (integrating with respect to $s$), say $A(x)$, with $x\rightarrow 0$ that you have to perform IBP but the number of iterations will never end. After a number of iterations, we have ...
1
vote
0answers
17 views

Order Size estimation of converging sum used for approximation of logarithm

I know it can be shown that $\log n=\sum_{i=1}^\infty \frac{(n-1)^i}{in^i}$ for $\forall n\in\Re$ where $n\ge1$ For given natural m, I tried to find the order size of k = f(m,n) in order for the ...
0
votes
1answer
13 views

Asymptotic notation basics

Say that we have the function $$ f(n)=kn, \, k>0 $$ does that imply the following? $$f(n) \in O(n), \, f(n) \in \Theta(n) \text{ and } f(n) \in \Omega(n)$$ I'm fairly new to these notations and am ...
1
vote
1answer
30 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 ...
0
votes
2answers
32 views

Find the asymptotics of $n(\frac{n-1}{n})^n$ [on hold]

Find the asymptotics of $n(\frac{n-1}{n})^n$. I know $f(x)$~ $g(x) $ if $lim\frac{f(x)}{g(x)}=1$ but I am unsure as to how I found $g(x)$ I found a solution $\frac{2n-1}{2e}$ but I am unsure where ...
0
votes
0answers
17 views

Justify Why Boundary Layer Exists at x=0

With part a of this question (I asked about latter parts before), does it suffice to find the outer solution and show that since both boundary conditions cannot be met, then there exists a boundary ...
3
votes
0answers
47 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: ...
0
votes
1answer
26 views

Question regarding complexity classes, what is O(N log N^2)

What "better-known" complexity class is equivalent to $O(N log N^2)$ By log power rule, $N log N^2$ = $N^2log N$ is there a further way to simplify this?
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
22 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? ...
5
votes
1answer
2k views

Hardy Ramanujan Asymptotic Formula for the Partition Number

I am needing to use the asymptotic formula for the partition number, $p(n)$ (see here for details about partitions). The asymptotic formula always seems to be written as, $ p(n) \sim ...
1
vote
0answers
39 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 ...
0
votes
2answers
28 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 ...
2
votes
0answers
28 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
34 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
16 views
2
votes
2answers
49 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
1answer
16 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 ...
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
32 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, ...
2
votes
1answer
53 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 ...
1
vote
1answer
117 views

sum over primes involving divisor function (variation of the Titchmarsh divisor problem)

Does there exist an asymptotic estimate for the following sum over primes $$ \sum_{p\leq x} \frac{\tau(p-1)}{p}\;, $$ where $\tau(n)=\sum_{d|n}1$ is the divisor function?
0
votes
1answer
28 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 ...
2
votes
2answers
74 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?
4
votes
1answer
58 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
2answers
54 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
37 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$ ...
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 ...
0
votes
0answers
30 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 ...
6
votes
4answers
194 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 ...
1
vote
3answers
36 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 ...
0
votes
1answer
17 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 ...
0
votes
2answers
55 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 ...
1
vote
1answer
20 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 ...
5
votes
2answers
79 views

Is it true that $ \sum_{t = 1}^T \frac{T-t}{ t+ \sqrt{T-t}} \in O(T) $?

Is the following true? $$ \sum_{t = 1}^T \frac{T-t}{ t+ \sqrt{T-t}} \in O(T) $$
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
29 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
22 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
2answers
92 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 ...
1
vote
1answer
33 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 ...
0
votes
0answers
6 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
37 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 ...
5
votes
1answer
816 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 ...