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

learn more… | top users | synonyms (1)

1
vote
1answer
158 views

Example of pairwise independent random process with expected max load $\sqrt{n}$. [closed]

Throw $n$ balls into $n$ bins. Each bin is selected uniformly at random but the process is only pairwise independent. Call the maximum number of balls in any bin the max load. Lemma 2 in these ...
2
votes
4answers
50 views

Finding growth bounds on Fibonacci Sequence

I've been working on this following problem: Find a constant $c< 1$ such that $F_n \leq 2^{cn}$ for all $n \geq 0$. I honestly have no idea where to begin on this. I've done plenty of proofs ...
2
votes
3answers
34 views

Help formulating a proof showing two lists can be merged with 2n-1 comparisons

I need some help formulating a proof that shows that two lists of size n can be merged in 2n - 1 comparisons. I understand the essence behind it, but have difficulty proving it mathematically. I ...
2
votes
0answers
298 views

Asymptotic Methods - Boundary Layer Problems

I am currently studying a course in Asymptotic and Perturbation Methods and we have recently started discussing "Boundary Layer problems". It is not clear to me, however, exactly what form "Boundary ...
5
votes
2answers
31 views

Big-$O$ for $\frac{1}{1-x}$

I would like to show as $x\rightarrow 0$ $$\frac{1}{1-x}= 1+x^2+x^3+\dots+x^n +O(x^{n+1})$$ My inclination is to multiply by $1-x$ to get: $1=(1-x)(1+x^2+\dots+x^n) +(1-x)O(x^{n+1})$ and then, for ...
0
votes
2answers
23 views

Proving the summation of a function as big theta of another function

Show that $\sum^n_i i^4\log^2i$ = $\Theta(n^5\log^2n)$ I am completely lost on how to solve this problem. I understand that $\Theta$ deals with the upper and lower bounds, so do we prove both big-oh ...
1
vote
0answers
73 views

Asymptotic distribution and stability?

I am working with asymptotic theory and I have some things I am unsure about. For example if one uses the Central Limit Theorem as an example: $\sqrt{n}\bigg(\bigg(\frac{1}{n}\sum_{i=1}^n ...
2
votes
1answer
21 views

Growth of modified binomial recurrence

The binomial coefficients $\binom{n}{r}$ satisfies $\binom{n}{r}=\binom{n-1}{r}+\binom{n-1}{r-1}$. This means it is a solution of the equation $f(n,r)=f(n-1,r)+f(n-1,r-1)$, with initial conditions ...
2
votes
1answer
22 views

Using $f=O(g)$ to compare $f^2$ and $g^2$

When we have $f = O(g)$, does this work? $f^2 = O(g^2)$? If I have $n^2 = O(n^3)$, I think that $n^4= O(n^6)$ so I think this is valid. What about $2^f vs 2^g$? Does $f = O(g)$ imply $2^f = O(2^g)$? ...
0
votes
1answer
20 views

Growth rate of $n3^n$ vs $4^n$

Does the latter grow faster? I'm assuming that if we have a^n vs b^n, if b>a then a = O(b), but if there is a n term in front of a does that change it?
0
votes
1answer
22 views

Growth of binomial recurrence with different initial conditions

The binomial coefficients $\binom{n}{r}$ satisfies $\binom{n}{r}=\binom{n-1}{r}+\binom{n-1}{r-1}$. This means it is a solution of the equation $f(n,r)=f(n-1,r)+f(n-1,r-1)$, with initial conditions ...
3
votes
0answers
45 views

Asymptotic expansion of a Fourier Transform as $\omega\rightarrow 0$

First of all, I do apologise if the question is not formulated in precise mathematical terms, but as a physics student I lack a formal background on rigorous functional analysis. Suppose we have a ...
2
votes
0answers
19 views

Multivariate Delta Method

If I have a $\sqrt{N}$ asymptotic normal estimator (call it $\boldsymbol{\theta}$, possibly a vector). Say I want to find the asymptotic distribution of $g(\boldsymbol{\theta})$ and suppose ...
2
votes
0answers
28 views

A necessary condition for boundedness in probability

I understand that it is straightforward to show (via Markov's inequality and standard arguments) that \begin{equation} E(X_n)=O(a_n) \end{equation} implies \begin{equation} X_n=O_P(a_n) \end{equation} ...
0
votes
2answers
90 views

Solve the recurrence $T(n) = 2T(n-1)+n^2$

Solve the recurrence $$T(1) = 1, T(2) = 1, T(3) = 1,T(n) = 2T(n-1)+n^2, n > 3$$ I have now, $$T(n) = 2T(n-1)+^2 $$ $$= 2(2T(n-2)+(n-1)^2+n^2$$ $$=4T(n-2)+2(n-1)^2+n^2$$ $$....$$ ...
1
vote
2answers
18 views

On estimating a prime related Diophantine equation related to a partition .

A friend gave me the following algebraic combinatorics question which I couldn't solve Let $p$ be a prime number and $f(p)$ the smallest integer for which there exists a partition of the set $\{2,3, ...
0
votes
1answer
40 views

Is square root of n the same as log n for order notation of an algorithm

Given the context of a basic prime number testing algorithm that has the simple optimization of limiting the potential factors to the range from 2 to the square root of the subject number (instead of ...
0
votes
1answer
31 views

Divisor number asymptotic? [duplicate]

I have got an interesting task, but I can't solve it: We use $d(n)$ as the number of divisors for the positive $n$ integer. We have: $$a(n)=\sum_{i=1}^n d(i)$$ How much is $a(n)$ asymptotic? $a(1) ...
1
vote
2answers
62 views

Asymptotic expansion of exp of exp

I am having difficulties trying to find the asymptotic expansion of $I(\lambda)=\int^{\infty}_{1}\frac{1}{x^{2}}\exp(-\lambda\exp(-x))\mathrm{d}x$ as $\lambda\rightarrow\infty$ up to terms of order ...
0
votes
2answers
140 views

Asymptotic integral expansion of $\int_{0}^{\pi/4}{d\theta \over \epsilon^2+\sin^2\theta}$ for $\epsilon \to 0$

I am studying how to evaluate the integral $$\int_{0}^{\pi/4}{d\theta \over \epsilon^2+\sin^2\theta}$$ as $\epsilon \rightarrow 0$ with asymptotic methods. The book perturbation methods by Hinch ...
5
votes
1answer
177 views

Integral asymptotic expansion of $\int_{0}^{\infty} \frac{e^{-x \cosh t}}{\sqrt{\sinh t}}dt$ for $x \to \infty$

$$\int_{0}^{\infty} \frac{e^{-x \cosh t}}{\sqrt{\sinh t}}dt$$ I'm trying to use Laplace's method to find the leading asymptotic behavior as $x$ goes to positive infinity, but I'm having some trouble. ...
1
vote
0answers
90 views

Find the Laplace approximation of $\frac{1}{2\pi} \int_{-\pi}^{\pi }e^{x\cos(\theta )}d \theta$ for $ x \to \infty$

Let's have integral $$ I(x) = \frac{1}{2\pi} \int \limits_{-\pi}^{\pi}e^{x\cos(\theta )}d \theta, \quad x \to +\infty . $$ How to use Laplace approximation for this integral and find first two ...
1
vote
3answers
60 views

How to evaluate this exponential fraction limit?

I am trying to determine if 3$^n$ grows faster than 2$^{2n}$. One way I found online to do this was, from Growth was to evaluate $\lim_{n\to \infty} \frac{3^n}{2^{2n}}$ and if that limit evaluates ...
0
votes
1answer
20 views

Prove that $\frac{f(n)+a}{g(n)+b} = O(\frac{f(n)}{g(n)})$

I was reading about algorithm analysis and I saw a similar simplification done in order to find the complexity. I became interested in proving that this simplification is formally correct but I am ...
1
vote
1answer
20 views

If $x$ is a $\chi^2_{N-n}$ RV. what is $x/N$ as N goes to infinity

We know that if we have $N-n$ gaussian iid RVs $\{e_i\}$ with mean $0$ and variance $1$, the RV $x = \sum e_i^2$ is $\chi^2$ distributed with $N-n$ degrees of freedom. We have $N$ larger than $n$. I ...
1
vote
1answer
17 views

A question regarding the order of an asymptotic estimate

Suppose that $m, n \in \mathbb{N}$ such that \begin{equation} m \cdot \log m = n, \end{equation} where the logarithm is in the natural base. How can we estimate the solution $m = m(n)$ ...
2
votes
1answer
91 views

What does the sign “$=$” exact meanings?

How can I understand the sign "$=$" from the following expression: $$\mathcal{o}f((x))=\mathcal{o}f((x))+\mathcal{o}f((x));$$ $$\mathcal{o}(kf((x)))=\mathcal{o}(f(x));$$ ...
0
votes
0answers
11 views

How would I compare these differential statements using Big O notation?

I am doing an econ problem. The question asks me to basically discuss in economic terms the effect of increasing or decreasing $\alpha$ on the function $$1= x^\alpha y^{1-\alpha}$$ Anyways, I've ...
0
votes
2answers
36 views

Asymptotic Algorithm General Approach to Finding $\Theta$ Bound

I'm working on the following asymptotic algorithm bounds problem Find a $\Theta$ bound for $f(n) = \frac{n^2}{2} - \frac{n}{2}$ So I could find the big-$O$ bound fairly easily $$ 0 \leq ...
0
votes
1answer
30 views

Floor function and little oh notation

Can we replace $o([x]^a)$ where $[x]$ is floor of $x$ and $a$ is a positive number with $o(x^{a})$? And can we replace $o(x^{a})$ with $o([x]^a)$?
0
votes
1answer
43 views

Confusion on Big $O$

I am so confused on the intuitive idea behind Big $O$ notation. $f(x)=O(g(x))$ iff there is a constant $C>0$ such that for large $x, |f(x)|\leq C|g(x)|$ and I have seen that in many places that ...
1
vote
1answer
32 views

How to show $n \sum_{k>n} (k^2 \log k)^{-1} \sim (\log n)^{-1}$?

How does one show that $$n \sum_{k>n} \frac{1}{k^2 \log k} \sim \frac{1}{\log n} \quad ?$$ Many thanks for your help.
1
vote
2answers
97 views

Number of distinct prime divisors of an integer $n$ is $O(\log n/\log\log n)$

I strongly believe that the claim is true; but I'm neither a mathematician nor speaking French and hope that somebody can confirm it, since related questions (here, here and here) either don't have an ...
0
votes
0answers
19 views

Approximate distribution of product of N normal i.i.d.?

Given $N>30$ i.i.d. $X\approx\mathcal{N}(\mu_X,\sigma_X^2)$, looking for: accurate closed form distribution approximation of $Y=\prod_{n=1}^{N}{X}$ asymptotic normal approximation of same ...
1
vote
1answer
65 views

Which way is best to solve: $T(n)=5T(n/5) + n\;?$

I'm not sure which way is best to solve $$T(n)=5T(n/5) + n$$ (recursion tree/master method/recurrence?) I would like some assistance, which way is easier and how can I be sure I got the right answer ...
2
votes
0answers
24 views

Biggest rate of growth of a sequence in $ℓ^2$

$ℓ^2$ is the space of complex sequences $u_n$ such that $\sum |u_n|^2$ converges. I'm wondering if there are asymptotic results known about such sequences. We have trivially $u_n=o(1)$. Are better ...
1
vote
0answers
34 views

If I colour $n$ vertices independently, randomly with $n^{(1-x)}$ colours, why is the size of the colour classes $(1+o(1))n^x$?

By $o(1)$, I mean 'little-o' of $1$. A paper I'm reading uses this result, but I can't see where it comes from. Thanks.
1
vote
1answer
23 views

Is this statement correct $f(n) = \theta(n) \land g(n) = \Omega(n) \Longrightarrow f(n)g(n) = \Omega(n^2)$?

I am having some difficulties understanding what does it mean to "and" $\theta(n)$ and a function $g(n)$, what does it mean in mathematical terms? Specifically, in the following example, I have to ...
0
votes
0answers
29 views

Show T(n)=T(n/5)+T(4n/5)+n/2 is $\Omega (n log n)$

I'm tasked with showing T(n)=T(n/5)+T(4n/5)+n/2 is Big-Omega n log n by drawing a recursion tree. The tree shows a lower bound with the following terms: n/2 ... n/10 ... n/50 ... etc. When I solve ...
1
vote
1answer
41 views

Asymptotic behavior of the confluent hypergeometric function

Consider the following function $$U(a,z)= \frac{1}{\Gamma(a)} \int^{\infty}_0 t^{a-1} \cdot (1+t)^{-a} e^{-zt} dt$$ My Try : Let $\tau= zt$, then : $$ U(a,z)= \frac{z^{-a}}{\Gamma(a)} \int^{\infty}_0 ...
0
votes
1answer
52 views

How rapidly does $\Gamma(x)$ diverge as $x$ approaches $0$?

Notoriously $$\lim\limits_{x\to0^{\pm}}\Gamma(x)=\pm\infty,$$ but can we be more precise (tightly) bounding from above $\left\lvert \Gamma(x) \right\rvert$ when $x$ is close to $0$? I could not find ...
4
votes
2answers
97 views

Laplace's method with nontrivial parameter dependency

I need to approximate the following integral using Laplace's method: $$ \int_0^{\infty} \frac{x^{\lambda} \lambda^{-x}}{(1+x^2)^\lambda} dx \\ = \int_0^{\infty} \exp\left(\lambda \log(x) - ...
0
votes
1answer
21 views

Asymptotic-Proof

I am looking at this questions and the proof for it and wondering how this works.Can anyone explain the answer to me or do you have any other way to answer this question.I am new to asymptotic ...
5
votes
1answer
64 views

Why does Titchmarsh say that we can move the derivative under $\frac{2}{\pi}\int_0^\infty \frac{\Xi(t)}{t^2 + \frac{1}{4}} \cosh(\alpha t) \, dt$

If we define the Riemann-Xi function as $$ \Xi(t) = \xi(\frac{1}{2} + it)$$ where $$\xi(s) = \frac{1}{2}s(s-1)\pi^{-\frac{s}{2}}\Gamma(\frac{s}{2})\zeta(s),$$ then according to Titchmarsh in his ...
1
vote
1answer
26 views

limiting variances of iid sample mean

In the book Statistical Inference (George Casella 2nd ed.), page 470, there is an example: $\bar{X}_n$ is the mean of $n$ iid observations, and E$X=\mu$, $\operatorname{Var}X=\sigma^2$. "If we take ...
1
vote
1answer
71 views

Is it possible to find the least common divisor of a two numbers that are not relatively prime in polynomial time?

As the question states: Is it possible to find the least common divisor of two number that are not relatively prime in polynomial time? If so, how? Thanks!
3
votes
0answers
36 views

Merten's function

I am tasked with applying the Wiener-Ikehara Theorem to achieve a bound of little o(x) on Merten's function $\sum_{n=1}^x \mu (n)$. My problem is the Wiener-Ikehara Theorem applies to Dirichlet series ...
0
votes
2answers
36 views
1
vote
0answers
39 views

Asymptotic Proof

Can someone explain this asymptotic proof to me.I am stuck at the inductive step and get lost around this step $2 × n! < (n + 1) × n!$ $$2n = o(n!)$$ True Proof: In order to $2n = o(n!)$ be true, ...