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
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
17 views

Determine asymptotic complexity of the code

I need to determine asymptotic complexive. ...
2
votes
2answers
52 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
24 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
36 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
54 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
121 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
65 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
57 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
31 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
210 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$ ...
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
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 ...
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 x+b_2x+O(\log^2x)$$...
0
votes
0answers
10 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 ...
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[ \...
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 ...
31
votes
5answers
715 views

A disease spreading through a triangular population

I have run into this problem in my research, which I'm presenting under a different guise to avoid going into unnecessary background. Consider a population that is connected in a triangular manner, ...
0
votes
1answer
13 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
85 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 $\...
2
votes
0answers
54 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
88 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$$...
4
votes
1answer
41 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 $...
7
votes
3answers
184 views

Arithmetic rules for big O notation, little o notation and so on…

There are many asymptotic notations like the big O notation: big Omega notation, little o notation, ... Thus there are many arithmetic rules for them. For example Donald Knuth states in Concrete ...
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 ...
0
votes
2answers
35 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 ...
0
votes
1answer
59 views

What is the pattern of the Stirling series?

It can be shown that: \begin{eqnarray*} n! = \left ( \frac{n}{e} \right )^n \sqrt{2 \pi n} e^{ \frac{B_2}{2n} + \frac{B_4}{4 \cdot 3 \cdot n^3} + \cdots + \frac{B_{2m}}{2 m ( 2m-1) ...
1
vote
1answer
20 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
3answers
140 views

Calculating Running Time (in seconds) of algorithms of a given complexity

I've tried to find answers on this but a lot of the questions seem focused on finding out the time complexity in Big O notation, I want to find the actual time. I was wondering how to find the ...
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
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
40 views

Can you get the average order of $ \left( 1+|\mu(n)| \right)^{M(n)} $, where $\mu(n)$ and $M(n)$ are the Möbius and Mertens functions, respectively

When yesterday I was interested in do a little study about the arithmetic function $$f(n)=\left( 1+|\mu(n)| \right)^{M(n)},$$ defined for integers $n\geq 1$, which $\mu(n)$ is the Möbius function and $...
0
votes
1answer
25 views

On a bound about $\sum_{n\leq n}\sqrt{\frac{x}{n}} \left[\sqrt{\frac{n}{x}} M \left(\frac{x}{n} \right) \right] $

From the fact that $f(x)= \left[f( x) \right]+ \left\{ f(x) \right\} $, where $ \left\{ x \right\} $ is the fractional part function, one can write by a direct substitution for the function $M(x)=\...
0
votes
1answer
7 views

Time complexity of modulo scenario

Something theoretical here. Say if I have two natural numbers $x$ and $y$. Both these numbers are upper-bounded by a third number $z$. ($O$($z$)) Now let's say I have a recursive modulo function ...