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

learn more… | top users | synonyms (1)

0
votes
2answers
41 views

Asymptotic evaluation of a quantity

Can we say that the following quantity (a recursion of logarithms): $W_{-1}(x)=\ln \cfrac{-x}{-\ln \cfrac{-x}{-\ln \cfrac{-x}{...}}}$ is $\Theta(\ln x)$? i.e., asimptotically upper and lower bounded?...
0
votes
0answers
9 views

Reference Books on Asymptotic theory of Statistics and Probability

Can anyone suggest me some good reference books on Asymptotic Theory of Statistics and Probability for students pursuing a post-graduate degree in Statistics ? It would be very much helpful if the ...
5
votes
1answer
56 views

Asymptotic expansion of $(1+\epsilon)^{s/\epsilon}$

I have taken the logarithm of this expression and computed the Taylor expansion of the $\log(1+\epsilon)$ term but by doing this we're required to calculate powers of this series when using the ...
2
votes
2answers
45 views

Estimate for a prime product.

Is there a bound for $$\prod_{i=1}^{m}\Big(1-\frac{1}{p_i}\Big)$$ where $p_i$ is $i$th prime? What if $m=O(\log n)$?
4
votes
1answer
46 views

Density of a set of numbers.

Firstly, I introduce a notation. $\Bbb{N}$ denotes the set of natural numbers, $0$ included. For $E \subseteq \Bbb{N}$ and $n \in \Bbb{N}$, I denote by $$\pi_E(n) = |E \cap \{ 1, \dots , n\}|$$ and $$...
0
votes
1answer
19 views

Finding the upper tight bound of a mathematical function. (Big O)

I am trying to understand Big-$O$ notation through a book I have and it is covering Big-$O$ by using functions although I am a bit confused. The book says that $O(g(n))$ where $ g(n)$ is the upper ...
5
votes
5answers
45 views

For some arbitrarily fast growing function $f$ and a strictly sublinear function $g$, can $g \circ \cdots \circ g \circ f$ always grow polynomially?

Given two functions $f, g: \mathbb{R}_{≥ 0} \to \mathbb{R}_{≥ 0}$ that are monotonically growing, with $g(x) \in o(x)$ (i.e. $g$ grows strictly sublinear), does there always exist an $m \in \mathbb{N}$...
1
vote
2answers
30 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}} &...
1
vote
2answers
18 views

How to calculate duration of event at different speeds

Specifically I want to figure out the formula which will tell me: how long will it take to watch this video (normal length $L$) at speed $x$. I think this will be asymptotic, no matter how fast you ...
-1
votes
2answers
54 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
37 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_{- ...
0
votes
1answer
22 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 then ...
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
34 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
17 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
33 views

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

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
20 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
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: $$\...
0
votes
1answer
29 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
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? ...
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 \frac{1}{4n\...
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 ...
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 ...
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. ...
2
votes
2answers
53 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
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 ...
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, ...
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 ...
1
vote
1answer
122 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
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 $...
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?
4
votes
1answer
66 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
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
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(...
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
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 ...
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 ...
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 ...
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 ...
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 ...
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
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$ ...