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
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 ...
1
vote
2answers
122 views

How is how $O(\log n)$ is a subset of $O(n^b)$?

This is an excerpt from a textbook I am reading: A number of useful shortcuts can be applied when using asymptotic notation. First: $O(n^{c_1}) \subset O(n^{c_2})$ for any $c_1 < ...
2
votes
1answer
201 views

Asymptotic Expansion of a Two Variable Function

How is the double asymptotic expansion defined? I can't seem to find it anywhere. Suppose $$f(x)\sim \sum_{n=0}^\infty a_n\phi_n(x)$$ as described in the Wikipedia aritcle. How is then for ...
2
votes
1answer
58 views

Showing that $\frac{1}{(1-\frac{\pi}{\sqrt{6n}})^n} = O(e^{\pi\sqrt{n/6}})$

Here's a small introduction on what I am doing skip to the %%%%%%%%%% if you just want the question. Definition: We say that $f(z) << g(z)$ if $|f(z)| \leq |g(z)| \quad \forall z \in D$. In ...
3
votes
1answer
56 views

Runtime Analysis, Coefficients in logarithms? Ignorable?

I had a question regarding when we can ignore constants during Big O analysis. If I had $f(n)=\log5x$ and $g(n)=\log100x$, would the constants $5$ and $100$ be ignorable when considering $n \to ...
1
vote
0answers
87 views

Solution by of nonlinear equation

$$\frac{\partial^2 u}{\partial t^2} - \frac{\partial^2 u}{\partial x^2} + \sin u = 0$$ From the sine-Gordon equation we can easily solve, \begin{equation} \phi(x) = \pm 4 \tan^{-1}\left[e^{\frac{x-t ...
2
votes
1answer
67 views

How to write this in big O notation?

I have a function $f(m,n)$ for which there exists a constant $\alpha<2$ such that, for fixed $m$, as $n\rightarrow\infty$, we have $f(m,n)\leq\alpha\sqrt{m/n}$, and for fixed $n$, as ...
0
votes
1answer
224 views

Asymptotic notation meaning in transitive relation

I'm attempting to prove the transitive relation on $\theta$ and I'm having trouble understanding the meaning of one of the symbols used. Here is the transitive relation: $f(n) = \theta(g(n)) ...
2
votes
2answers
227 views

$\sum _{p\leq n}\frac{1}{p}=C+\ln \ln n+O\left(\frac{1}{\ln n}\right)$

$\sum _{p\leq n}\frac{\ln p}{p}=\ln n+O(1),n\geq 2,$ where $p$ is a prime number, prove: $$\sum _{p\leq n}\frac{1}{p}=C+\ln \ln n+O\left(\frac{1}{\ln n}\right)~~~(1)$$ one examination ...
0
votes
1answer
41 views

vertical asymptotes of (limit of |x-3|/(|5-x|-|1-x|) x->3-)

vertical asymptotes of (limit of |x-3|/(|5-x|-|1-x|) x->3-) As the title said I'm not sure whether this equation have vertical asymptotes or not ...
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
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 ...
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
2
votes
0answers
156 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.
4
votes
2answers
263 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 ...
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 ...
3
votes
2answers
174 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
265 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 ...
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 ...
0
votes
1answer
285 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 ...
1
vote
1answer
60 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- ...
25
votes
1answer
488 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
1answer
72 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
481 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 ...
0
votes
4answers
87 views

Solving a simple ${\cal O}(N\log N)$ recursive equation.

A recursive divide and conquer algorithm runs for input size $N$ in $T(N)$ time where $$ \begin{align} T(1)&={\cal O}(1) \\ T(N)&={\cal O}(1)+2T(N/2)+{\cal O}(N) \\ ...
1
vote
1answer
41 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 ...
5
votes
3answers
850 views

Asymptotics of terms and errors in Stirling's Approximation

I have two related questions. Both are related to the asymptotics of Stirling's approximation, which is why I have included them in the same question. I will separate the questions if it is deemed ...
2
votes
3answers
107 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: ...
0
votes
2answers
866 views

Big Theta equivalence classes and proofs

I have a series of equation and I need to find which are in the same big theta equivalence class and order them. I am super confused by big theta. The equations are: $\ln(2x)$ $\ln(x)$ $x^2+2x$ ...
2
votes
1answer
909 views

Method of dominant balance

Find the leading asymptotic behaviour as $x \rightarrow \infty$ of $$x^2y'' + (1 + 3x)y' + y = 0 $$ Can someone kindly explain me how to solve this problem? Im learning asymptotic analysis, and I ...
4
votes
0answers
256 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 ...
1
vote
2answers
91 views

Computing limits with Asymptotics (Book suggestion)

Is there a standard book or reference to learn techniques of computing limits similar to the answer of this problem: How does one easily compute the limit of $a_n=(n\cdot \ln(\frac{n+1}{n}))^n$? ...
0
votes
1answer
147 views

Is there any “nice” function whose MacLaurin series has certain properties?

In learning about asymptotic expansions of functions, I've encountered several problems where a particular pattern of powers is coming into play, and I'm finding functions that I can readily show to ...
10
votes
3answers
293 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 ...
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 ...
3
votes
1answer
70 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 ...
6
votes
2answers
204 views

Estimating rate of blow up of an ODE

Suppose I have a differential equation $x'=f(x)$ and $f(x)>0$ grows super-linearly. I.e., $\lim_{|x| \rightarrow \infty} |f(x)|/|x| \rightarrow \infty$. Several related questions: (1) Can I ...
3
votes
2answers
132 views

Help Proving that $\frac{(1+\frac{1}{t})^t}{e} = 1 -\frac{1}{2t} + O(\frac{1}{t^2})$ for $t\geq 1$

I'm trying to prove the asymptotic statement that for $t\geq 1$: $$\frac{(1+\frac{1}{t})^t}{e} = 1 -\frac{1}{2t} + O(\frac{1}{t^2})$$ I know that $(1+\frac{1}{t})^t$ converges to $e$ and the right ...
3
votes
1answer
974 views

Orders of Growth between Polynomial and Exponential

What is known in contemporary mathematics about orders of growth for functions that exceed any degree polynomial, but fall short of exponential? This is a subject for which I've found little ...
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
226 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
103 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 ...
1
vote
0answers
366 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 ...
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 ...
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: ...
1
vote
1answer
355 views

Comparing asymptotic order of logarithmic functions

If I have two complicated logarithmic functions, say $\sqrt{\log n}$ and $\log(n(\log n)^3)$, and I have to compare them in terms of their asymptotic order. How do I do that? Do I have to create ...
1
vote
1answer
123 views

Multivariable asymptotic analysis?

Show that $k \ln k = \Theta (n)$ implies $k = \Theta (n /\ln n)$. Thanks for the help.
0
votes
1answer
112 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}$ ...