# Tagged Questions

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

52 views

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 ...
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, ...
29 views

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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$ ...
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 ...
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.
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)$$...
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 ...
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 ...
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 ﬁnal case to try is to ...
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 ...
32 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.