# Tagged Questions

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

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?...
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 ...
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 ...
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)$?
46 views

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 ...
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)$ ...
37 views

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?
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 ...
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 ...
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? ...
2k views

18 views

### Determine asymptotic complexity of the code

I need to determine asymptotic complexive. ...
53 views

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 $$\... 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 ... 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 ... 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, ... 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 ... 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? 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 ... 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? 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 ... 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 ... 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(... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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) 
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 ...
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$ ...