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

learn more… | top users | synonyms (1)

2
votes
1answer
78 views

Limit of a Permutation: $P(N,n)$ for $n\ll N$

I'm trying to prove that, for $N\gg n$, $P(N,n)=\frac{N!}{(N-n)!}\approx N^{n}$ I've tried two approaches, 1 ...
0
votes
2answers
85 views

For $f(n) = \log n$ and $g(n) = n^c$, where $0 < c < 1$, is it always true that $f$ is $O(g)$?

In complexity analysis, basic functions you encounter are functions like $f_1(n) = \log n$, $f_2(n) = n^2$ and $f_3(n) = n^3$. It is fairly obvious to me that $f_1$ is $O(f_2)$ and $O(f_3)$, but it is ...
2
votes
0answers
163 views

Convergence to non-degenerate limit.

If $X_1,X_2......$ follow Poisson$(λ)$. Can we find suitable constants $a_n$ and $b_n$ such that $a_n(Y_n - b_n)$ converges to a non degenerate limit where $Y_n = (1 - \frac{1}{n})^{n\bar{X}_n}$. I ...
0
votes
3answers
47 views

$c^3 \ll l^3$ prove that $\sqrt{l\over{l+c}}+\sqrt{l \over{l-c}}=2+{3c^2\over 4l^2} $

If $c^3$ is negligible compared to $l^3$, how may I prove that $$\sqrt{l\over{l+c}}+\sqrt{l \over{l-c}}=2+{3c^2\over 4l^2}?$$ This might be a problem involving binomial series.
2
votes
0answers
59 views

Bounds on a rapidly increasing sequence

I read about a sequence similar to this one here on Stack Exchange a while back, somebody used it as an example for something that I can't recall! However, when I read about it it made me come up with ...
3
votes
2answers
148 views

On proving the convergence of $1/n^2\sum_{1\le k\le n}\varphi(k)$

Let $$\Phi_n=\frac{1}{n^2}\sum_{k=1}^n\varphi(k).$$ How one can show that $\Phi_n$ is convergent sequence? (Here, $\varphi$ denotes the Euler's totient function.) And please, without any monster ...
0
votes
1answer
42 views

Transforming a sequence of i.i.d. variables so that its asymptotic distribution is non-degenrate

Suppose $X_1,X_2,\cdots$ are i.i.d. $U(0,\theta)$ random variables. Can you suggest a function $h$ of $X_1,\cdots,X_n$ and constants $a_n$ and $b_n$ such that ...
0
votes
0answers
40 views

Testing hypothesis about variance of non-normal population

Let $X_1,X_2,\cdots$ be i.i.d. from a distribution $F$ with mean $0$ and unknown variance $\sigma^2$ and having four moments. A common test for testing $H_0:\sigma^2=1$ vs $H_1:\sigma^2>1$ is to ...
5
votes
1answer
621 views

Asymptotic correlation between sample mean and sample median

Suppose $X_1,X_2,\cdots$ are i.i.d. $N(\mu,1)$. Show that the asymptotic correlation between sample mean and sample median (after suitably centering and renormalization) is $\sqrt{\frac{2}{\pi}}$.
3
votes
2answers
178 views

When does L'Hopital's rule pick up asymptotics?

I'm taking a graduate economics course this semester. One of the homework questions asks: Let $$u(c,\theta) = \frac{c^{1-\theta}}{1-\theta}.$$ Show that $\lim_{\theta\to 1} u(c) = \ln(c)$. Hint: ...
2
votes
1answer
278 views

Can anyone derive the formula for the expansion $(x + \Delta x)^{n}$ that uses Big O notation? [duplicate]

There is a formula that describes this expansion using big O notation, I'm very curious on how this is derived. I also understand that the order term may very depending on what $\Delta x$ approaches ...
0
votes
1answer
295 views

Explanation of the binomial theorem and the associated Big O notation

I'm currently following the MIT Single Variable lectures online and the professor states that the binomial theorem for the expansion $(x + \Delta x)^{n} = x^{n} + nx^{n-1}\Delta x + O((\Delta ...
4
votes
1answer
3k views

Upper bound for $T(n) = T(n - 1) + T(n/2) + n$ with recursion-tree [duplicate]

I'm reading through Introduction to Algorithms, 3rd ed. and I got stuck on the following recurrence (exercise 4.4-5): $$T(n) = T(n - 1) + T(n/2) + n$$ The exercise asks you to find the upper bound ...
4
votes
2answers
268 views

Asymptotic expansion of a function $\frac{4}{\sqrt \pi} \int_0^\infty \frac{x^2}{1 + z^{-1} e^{x^2}}dx$

How to find the asymptotic expansion of the following function for large values of $z$. $$f_{3/2}(z) = \frac{4}{\sqrt \pi} \int_0^\infty \frac{x^2}{1 + z^{-1} e^{x^2}}dx $$ I have to get something ...
1
vote
1answer
61 views

Repeated Bernoulli Trials, Wins-Losses

Consider $$X(t)=\mbox{Number of wins} - \mbox{Number of losses}$$ for $t$ Bernoulli($\theta$) trials. I calculated that $$P(X(t) = x) = {t \choose (t-x)/2} \theta^{\frac{t+x}{2}} (1- ...
4
votes
1answer
75 views

Is there a “natural” subsequence of positive integers $k_1 < k_2 < \ldots$ such that $\sum_{i=1}^n \frac{1}{k_i} = \Theta (\log \log \log n)$?

The harmonic series partial sums grow like $\log n$, and the sum of inverses of the first $n$ primes grows like $\log \log n$. Is there an example of a "nautral" subset of the positive integers (say ...
3
votes
5answers
494 views

Provide an algorithm $O (n ^ 3 \log n)$, any example?

Provide an algorithm computing performance $O (n^3 \log n)$. Your algorithm should contain only simple operations. Any idea of how to approach this problem?...I am studying for the computer science ...
4
votes
1answer
451 views

Can a curve be an asymptote?

$f(x)=x^3+\frac{3}{x-1}$ This was the question given to me.I replied that $f(x)$ will have only a single vertical asymptote of $x=1$. My teacher told that there'll be be two asymptotes.One is the ...
8
votes
4answers
565 views

The asymptotic expansion for the weighted sum of divisors $\sum_{n\leq x} \frac{d(n)}{n}$

I am trying to solve a problem about the divisor function. Let us call $d(n)$ the classical divisor function, i.e. $d(n)=\sum_{d|n}$ is the number of divisors of the integer $n$. It is well known that ...
5
votes
2answers
517 views

Inverse of sparse matrix is not generally sparse

I have a question regarding inverse of square sparse matrices(or can be restricted to real symmetric positive definite matrices). I encountered several times the web pages which states that the ...
1
vote
1answer
42 views

Limiting Distribution of the given function

Can someone please help me in finding the limiting distribution of $$\frac{n(X_1X_2 + X_3X_4+\cdots+X_{2n-1}X_{2n})^2}{(X_1^2 + X_2^2+\cdots+X_{2n}^2)^2}$$ where $X_i$ are iid standard normal ...
2
votes
3answers
108 views

Need an asymptotic function that's going to have a specific shape

I'm looking for a function y = f(x) that grows quickly at first, and slowly later, asymptotically approaching 100. I need it to hit certain specific points... What I need is: ...
2
votes
1answer
78 views

Asymptotic solving of a hyperbolic equation

The solition and anti-solition nonlinear equation is given as: My problem is that, how do we get the next equation after considering asyptotic behaviour? Resource: (solition) at page 38
25
votes
1answer
501 views

Power towers: to infinity and all the way back

In the following, let $n$ be a positive integer, all other variables be real (furthermore, $a>1$), all functions be real-valued, and logarithms of negative arguments be undefined. Let ...
4
votes
0answers
270 views

An entire function of strict order 2

Here is a problem from Stein and Shakarchi Complex Analysis, can somebody help me to solve it? I guess we can use Phragmen-Lindelof theorem but I don't know the exact way. Suppose $f(z)$ is an entire ...
10
votes
3answers
295 views

Estimate $\displaystyle\int_0^\infty\frac{t^n}{n!}e^{-e^t}dt$ accurately.

How can I obtain good asymptotics for $$\gamma_n=\displaystyle\int_0^\infty\frac{t^n}{n!}e^{-e^t}dt\text{ ? }$$ [This has been already done] In particular, I would like to obtain asymptotics that ...
2
votes
1answer
79 views

asymptotic behaviour of coefficients in nonnegative matrix iteration

Let $A$ be a square matrix with nonnegative integer coefficients. Is there a simple way to prove that there is a "period" $d$ such that for all $0\leq r<d$, the coefficient $a_{i,j,n}$ at position ...
3
votes
1answer
71 views

Prove that $F_{x^{n+1}} \sim 5^{\frac{x-1}{2}}F_{x^n}^x \forall x,n \geq 1$, holding either variable constant while the other goes to infinity

I noticed from looking at the prime factorizations of some Fibonacci numbers that all those with an index equal to a power of 5 divided that power of five, a property not guaranteed by the strong ...
5
votes
1answer
198 views

Showing a Lebesgue integral exists, while another doesn't.

Consider $$f_p(x)=x^p \exp\left(-x^8\sin^2x\right)$$ I have to show that $f_2\in\mathscr L(0,+\infty)$ whilst $f_3\notin \mathscr L(0,+\infty)$. Now, I am looking at the case $p=2$. The problematic ...
2
votes
1answer
60 views

Growth rate of Taylor convergents near pole

For any fixed $z_0\in\mathbb{C}\setminus \{0\}$ and $\beta\in\mathbb{R}^{+}$, prove that $$\left.T_n\left(\log^{\beta}z;z_0\right)\right|_{z=0}\sim\log^{\beta} n$$ Note: I observed that this holds ...
2
votes
1answer
69 views

Asymptotic expansion of $\ln\left(\frac{x+a}{x-a}\right)$ in form of $\sum\limits_{n=0}^\infty a_n \left(\frac{1}{x}\right)^n$?

How can I find an expansion for $f(x)=\ln\left(\dfrac{x+a}{x-a}\right)$ in terms of powers of $x$, in the form of: $$f(x)=\sum_{n=0}^\infty a_n \left(\frac{1}{x}\right)^n$$ When I try a Taylor ...
0
votes
1answer
232 views

Asymptotic expansion of $\exp(-ax)\,\cosh(bx)$ or $\exp(-ax)\,\sinh(bx)$

I would like to understand the behaviour of $$\exp(-ax)\,\cosh(bx)$$ or $$\exp(-ax)\,\sinh(bx)$$ for large $x$, provided that $a,b>0$ and $a>b$ or $a<b$.
5
votes
0answers
104 views

Binomial asymptotic.

Is there any "direct" proof of the following asymptotic inequality: let $\alpha\le 1$ and consider $$Q_n(x)=\sum_{k=1}^n\frac{\alpha(\alpha+1)(\alpha+2)\cdots(\alpha+k-1)}{k!}x^k$$ Then, $$\int_0^1 ...
0
votes
2answers
184 views

Probability in ball coloring

You have exactly $n^2$ balls each one of which can be colored in one of $n^2$ ways. That is total colors is $n^2$ but I am not saying all the $n^{2}$ balls are distinctly colored. However assume each ...
1
vote
0answers
377 views

Relation between the exponential function and the modified bessel function of second kind

I found the following sentence at the wikipedia page : Unlike the ordinary Bessel functions, which are oscillating as functions of a real argument, Iα and Kα(this is the mod. bessel function of the ...
0
votes
1answer
114 views

Big O, Big Omega - getting this problem wrong, need understanding

I'm not sure I understand what to do here. Will someone help me understand how to determine what these recurrence relations are Big-O or Big-Omega of? Problem $a_0 = 0$ and $a_n = 1 + a_{n-1}$ ...
18
votes
6answers
1k views

Is there a slowest rate of divergence of a series?

$$f(n)=\sum_{i=1}^n\frac{1}{i}$$ diverges slower than $$g(n)=\sum_{i=1}^n\frac{1}{\sqrt{i}}$$ , by which I mean $\lim_{n\rightarrow \infty}(g(n)-f(n))=\infty$. Similarly, $\ln(n)$ diverges as fast as ...
2
votes
2answers
61 views

Order structure of asymptotics

Consider the set $A = \{\theta(f) \mid f : \mathbb{R} \rightarrow \mathbb{R},\;f\,\text{non-decreasing}\}$ where $\theta(f)$ denotes the set of functions which are asymptotically within a constant ...
5
votes
1answer
174 views

Strange Recurrence: What is it asymptotic to?

So I have the following recurrence relation for the growth rate of an algorithm: $T(n)$ = time taken by algorithm to solve problem of size n: $$T(n) = T(n-1) + T(\lceil(n/2)\rceil)$$ Clearly this ...
3
votes
2answers
71 views

Prove: For all $n\geq 1$, $a_{n+1}-a_n<8^ka_n^{\left(1-\frac{1}{k}\right)^3}$.

Set $S=\left\{\left.x^k+y^k+z^k\right|x,y,z\in Z^+\cup \{0\}\right\}$, k is a positive integer, sort elements of $S$ increasingly, that $a_1<a_2<a_3<\text{...}<a_n<\text{...}$. Prove: ...
3
votes
0answers
111 views

Exponentials of chi-squared random variables (and their sums)

Let $X_1,X_2,\ldots,X_n$ be a sequence of i.i.d. chi-squared random variables with $t$ degrees of freedom, i.e. $X_i\sim\chi^2_t$. I am wondering what is known about the distribution of ...
1
vote
1answer
225 views

Simple confusion about $\vartheta(x)$

By definition $\vartheta(x) \leq \psi(x). \hspace{20mm}(1) $ and also we know $\frac{\psi(x)}{x} \sim \frac{\vartheta(x)}{x},\hspace{45mm}(2) $ Littlewood's result that, for large x, successively ...
3
votes
1answer
214 views

Using the definition of big-oh notation, show that for any $k,\gamma>1$, $n^k=O(\gamma^n)$.

This question had been on my midterm in a course I took last year: Prove that for any $k,\gamma>1$, $n^k=O(\gamma^n)$. Intuitively, this makes sense. Even the fastest exponential algorithm ...
0
votes
2answers
70 views

Root of an exponential equation

Let $0 \le a \le 1$ and $-\infty < b < \infty$. I am looking for a solution of the exponential equation. $$ a^x + abx = 0. $$ I guess closed form expression of the root in terms of $a$ and $b$ ...
1
vote
2answers
652 views

Figuring out which functions are Big-O of other functions (of a of 9 different functions). Where do I start?

Problem I need to arrange the following functions in order, so that each function is big-oh of the next function. Functions Attempt @ Solution Understanding: I don't understand what to do here. ...
2
votes
3answers
372 views

Big $\Omega$ question! Prove $(n-1)(n-2)(n-3)$ is $\Omega(n^3)$

Problem Prove $(n-1)(n-2)(n-3)$ is $\Omega(n^3)$. Attempt @ Solution $f(n) = n^3(1-6/n+11/n^2-6/n^3)$ $g(n) = n^3$ Show that there exists a $C > 0$ and $n_0$ such that $f(n) \ge Cg(n)$ for all ...
4
votes
4answers
134 views

Prove that $(n+1)(n+2)(n+3)$ is $O(n^3)$

Problem Prove that $(n+1)(n+2)(n+3)$ is $O(n^3)$ Attempt at Solution $f(n) = (n+1)(n+2)(n+3)$ $g(n) = n^3$ Show that there exists an $n_0$ and $C > 0$ such that $f(n) \le Cg(n)$ whenever $n ...
1
vote
1answer
78 views

Does $f'(x) \in o(g'(x))$ imply $f(x) \in o(g(x))$ for monotonically increasing $f$ and $g$?

The title says it all. This seems intuitively true to me, but I'm not sure how one would go about proving this. (I'm asking because I'm trying to show that $x^n \in o(x^{n+1})$ for all natural $n$, ...
4
votes
3answers
126 views

Convergence of partial sums of real sequences

For all $i\in\mathbb{N}$, let $(a_{i,n})_{n\in\mathbb{N}}$ be a real sequence that tends to $0$ for $n\rightarrow\infty$. It holds also that $|a_{i,n}|\leq1$ for all $i,n\in\mathbb{N}$. Is it possible ...
0
votes
1answer
100 views

infinite sum with each summand converging to zero almost surely

Suppose $X_n$ is a random variable such that $X_n=O(b_n)$ almost surely, with $b_n\to 0$ as $n\to \infty$. Let $C$ be a real constant and $S_{j,k}(X_n)=\sum_{i=j}^kC^iX_n^i$ for ...