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

learn more… | top users | synonyms (1)

4
votes
0answers
172 views

Understanding Newman's proof of the prime number theorem

I am trying to understand D.J. Newman's proof of the prime number theorem, as presented by D. Zagier. I am not too familiar with analysis, and so there are some things I don't understand. In (III), ...
7
votes
1answer
200 views

Conjecture: The following sum is asymptotic to $\sqrt{9πm/8}$

Consider the following sum, known as Ramanujan's Q-function: $$\begin{align} Q(m) &= 1 + \frac{m-1}{m} + \frac{(m-1)(m-2)}{m^2} + \cdots + \frac{(m-1)(m-2) \cdots 1}{m^{m-1}} \\ &= \sum_{n ...
3
votes
1answer
63 views

Approximating an integral with elementary functions

Consider the integral $$\int_1^\infty\frac{\exp(-nx)}{x}dx$$ We get:$$\int_1^\infty\frac{\exp(-nx)}{x}dx=n\int_ n^\infty\frac{\exp(-x)}{x}=nE_1(n)$$ My question is, can we approximate this integral ...
7
votes
1answer
93 views

An asymptotic integral inequality

Suppose $f:\mathbb{R}\to\mathbb{R}$ is a continuous function, $g(x)=xf(x)-\int_0^xf(t)\ dt$, and we have $f(0)=0$ and $g(x)=O(x^2)$ as $x\to0$. Is it true that $f(x)=O(x)$ as $x\to0$ ?
0
votes
2answers
98 views

Why is big-Oh multiplicative?

If $f$ is $O(g)$ over some base, this means that $f(x) = \beta(x)g(x)$, where $\beta$ is eventually bounded. So this means that eventually, $f$ is at most $c$ times $g$, where $c$ is some constant. ...
0
votes
1answer
29 views

Reduce Lethargy Equation

I need to prove that $$1-\frac{(A-1)^2}{2A}\ln \frac{A+1}{A-1}$$ approximately equals $\dfrac{2}{A+2/3}$. I think that we can expand the $\ln$ to $2(1/A+1/(3A^3)+\dots)$ and so the first term ...
3
votes
0answers
67 views

Limit of a sum (no probabilities)

Show that $$\lim_{n\to+\infty}\left(\frac{2}{3}\right)^n\sum_{k=0}^{[n/3]}\binom{n}{k}2^{-k}=\frac{1}{2}$$ without using probabilities. $[\;\cdot\;]$ denotes the integer part.
0
votes
1answer
66 views

Joint distribution of sample quantiles

Suppose we have iid sample of size n from the distribution function of $F$ which has a continuous density $f$. How can I get the large sample joint distribution of p and q sample quantiles ? Thanks ...
2
votes
1answer
531 views

Bounding the modified Bessel function of the first kind

i'm looking for an upper bound for the modified Bessel function of the first kind of a +ive real argument. It seems that it satisfies the inequality : $$I_{n}(x)\leqslant \frac{x^{n}}{2^{n}n!}e^{x}$$ ...
2
votes
1answer
62 views

Asymptotics at the origin of the convolution with an approximation to the identity.

In short, I am trying to find sufficient conditions for an approximation to the identity function $K_h$ so that, for $h$ small enough and fixed, the asymptotics at the origin of an $L^1 \cap L^2$ ...
5
votes
2answers
212 views

Interval of convergence of $\sum\limits_{n\geq0} \binom{2n}{n} x^n$

We consider the power series $\displaystyle{\sum_{n\geq0} {2n \choose n} x^n}$. By Ratio Test, the radius of convergence is easily shown to be $R=\frac{1}{4}$. For $x=\frac{1}{4}$, Stirling ...
8
votes
3answers
470 views

the following inequality is true, but I can't prove it

The inequality $$\sum_{k=1}^{2d}\left(1-\frac{1}{2d+2-k}\right)\frac{d^k}{k!}>e^d\left(1-\frac{1}{d}\right)$$ holds for all integer $d\geq 1$. I use computer to verify it for $d\leq 50$, and find ...
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) \\ ...
0
votes
1answer
57 views

How would you best describe the rate of growth of the function $f(x) = cxr^x$?

Consider the function $f(x) = cxr^x$, where both $r$ and $c$ are constants and we have cases: (a) $r<1$, (b) $r>1$. Regarding terminology, how would you best describe the asymptotic growth of ...
0
votes
1answer
49 views

Looking for a way to find the proportional growth rate in time for any given notation

I am wondering if there is a straight forward way to illustrate the proportional growth rate in time (or space) for any given notation such as $O(n^2)$ or $O(logn)$? My initial thought is that ...
4
votes
1answer
155 views

Estimate the scale of $e^{-(m+1) t} \sum _{k=0}^{\infty } \frac{t^k}{k!}\left(\sum _{r=0}^k \frac{t^r}{r!}\right)^{m}$

I would like to estimate the scale of the following series, $$S(m,t)=e^{-(m+1) t} \sum _{k=0}^{\infty } \frac{t^k}{k!}\left(\sum _{r=0}^k \frac{t^r}{r!}\right)^{m},$$ where $e$ is the base of ...
0
votes
1answer
161 views

Why $O(\epsilon^{-1})\ll O(\epsilon^{-3/2})$

When looking for the approximate roots of $\epsilon^2x^6-\epsilon x^4-x^3+8=0$, since this is a single perturbation problem, we need to track down the three missing roots, so we consider all possible ...
2
votes
1answer
110 views

Solving $f_n=\exp(f_{n-1})$ : Where is my mistake?

I was trying to solve the recurrence $f_n=\exp(f_{n-1})$. My logic was this : $f_n -f_{n-1}=\exp(f_{n-1})-f_{n-1}$. The associated differential equation would then be $\dfrac{dg}{dn}=e^g-g$. if ...
0
votes
1answer
91 views

How to get $e^{\sqrt{\log (x)}} \leq e^{log(x)}=x \leq x^n$?

Hi i was browsing through various asynptotic questions and got stuck in the mid due to the following daubt in the answer given in the link: Prove that $e^{\sqrt{\log x }}=O(x^n)$. How beni got: ...
1
vote
1answer
230 views

Big-O Notation and Algebra

This is my first question here. Trying to simplify the following. $$f = O\left(\frac{5}{x}\right) + O\left(\frac{\ln(x^2)}{4x}\right)$$ I give it a try as follows. $$\begin{align} f &= ...
2
votes
1answer
74 views

Big-Oh Notation

I'm given to the following relationship: $$C(x) = C(\lfloor(\frac x2)\rfloor) + x, C(1)=2$$ I do not understand how my teacher says to calculate big O. Any help to start?
1
vote
1answer
114 views

order of magnitude analysis

Could anyone explain how to keep track of the error terms when solving an integral approximately? For example consider to evaluate the integral $\int_0^{\pi/2}\frac{\cos^2xdx}{x^2+\epsilon^2}$ as ...
2
votes
0answers
51 views

Solving $B(n)=3B(\frac{n}{\log_{2}n}) +n$ using master theorem.

First of all sorry if this has been posted before, I found lots of master theorem questions on the search but not one like this. I am familiar with master theorem but a little uncomfortable with ...
0
votes
1answer
43 views

Complexity of Code Snippet Without Knowing A Function?

I have the code snippet: int const n = 300; int nArr[n]; for(int i = 0; i<n; i++) { if(i >x) copyPrevious(nArr,i); } I need to find the complexity ...
2
votes
4answers
220 views

How does one derive $O(n \log{n}) =O(n^2)$?

I was studying time complexity where I found that time complexity for sorting is $O(n\log n)=O(n^2)$. Now, I am confused how they found out the right-hand value. According to this $\log n=n$. So, can ...
6
votes
3answers
155 views

Approximating the roots of $\epsilon^{2}x^{3}+x+1$

I saw the following in my lecture notes, and I am having difficulties verifying the steps taken. The question is: Assuming $0<\epsilon\ll1$ find all the roots of the polynomial ...
1
vote
1answer
77 views

Estimate the scale of the power series with Poisson pdf-like terms

Sorry to bother you, but I guess that this question is not appropriate for MO, so I repost it here hoping that someone could give me a clue. I would like to have an estimate for the series $$P(t) = ...
2
votes
2answers
135 views

Does $f(\epsilon)=o(\epsilon\ln(\epsilon))$ imply $\frac{f(\epsilon)}{\epsilon}=o(1)$?

I have the following homework question: Does $f(\epsilon)=o(\epsilon\ln(\epsilon))$ imply $\frac{f(\epsilon)}{\epsilon}=o(1)$ ? It doesn't seem correct to me, using the definition I could only ...
3
votes
0answers
76 views

Definition of small $o$

In one of my homework assignments (in intro to applied mathematics) there is the following definition: Given two functions $f(\epsilon),g(\epsilon)$ that are defined in $D=(0,\epsilon)$ we say ...
0
votes
4answers
3k views

Big-O: Prove $2^n$ is $O(n!)$ [duplicate]

I am a little stuck trying to prove that $2^n$ is $O(n!)$. Obviously, I can tell in a few ways that this is the case. For one, based on Big-$O$ hierarchy, the exponential is beneath the factorial in ...
1
vote
1answer
290 views

floors and ceilings in Master theorem

I am trying to go through the proof of the Master Theorem in Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, "Introduction to Algorithms (2nd or 3rd Ed.)" where it shows ...
3
votes
1answer
177 views

Asymptotics of a summation over real valued functions

Let $f$ and $g$ be integrable in $[0,1]$ and $(-\infty, \infty)$ respectively. Let $a_k$ be a divergent series of positive terms and $S_k = a_1 + a_2 + \ldots + a_k$ such that the following ...
6
votes
2answers
114 views

Prove $\log x!$ is $\Omega (xlogx)$

Find a positive real number $C$ and a nonnegative real number $x_o$ such that $Cx$$\log x$ $\leq$ $\log x!$ for all real numbers $x > x_o$. I tried to expand $\log x!$ into $\log 1 + \log2 +\log3 ...
-1
votes
3answers
115 views

Calculate big-$\Theta$ for $T(x) = \log(x2x!)$

$T(x) = \log(x2x!)$ use the property of log, $\log(x2x!)$ is equivalent to $\log(2x) + \log(x!)$ My approach is to prove big-$O$ and big-$\Omega$ for $T(x)$,then big-$\Theta$ just follows. If I ...
1
vote
1answer
206 views

Is there a function that grows asymptotically faster than the Busy Beaver numbers?

Is there a function that grows asymptotically faster than the Busy Beaver numbers? That is, I know that BB(n)^n grows faster than ...
5
votes
2answers
345 views

Big-O notation, prove the following: $\sum\limits_{k=3}^n(k^2 - 2k)$ is $O(n^3)$.

Use the definition of Big-O notation to prove the following: $\sum\limits_{k=3}^n(k^2 - 2k)$ is $O(n^3)$. Can someone please give me some hints on how to expand $\sum\limits_{k=3}^n(k^2 - 2k)$?
1
vote
4answers
329 views

How is “n+n/2+n/4…1” equal to “2n-1” using the formula for geometric series?

I never knew not having good knowledge of basic maths will be so crippling!! So please help me out this time. I'll be working on my maths from today on. I was discussing about complexity of an ...
2
votes
2answers
158 views

asymptotic infinity

I am very very new to math as a whole, so please excuse my n00biness. I read: ...
1
vote
1answer
185 views

Asymptotic analysis - if f(n) = Ω(g(n)), how to prove ln(f(n)) = Ω(ln(g(n)))?

Is the following statement true, if so, how can I prove it? if f(n) = Ω(g(n)), is also true that ln(f(n)) = Ω(ln(g(n)))? Since ...
1
vote
1answer
44 views

Cancellation of Asymptotics

Suppose $f,g,h$ are real functions defined on a neighborhood of $\infty$ such that $f\circ g=\Theta(f\circ h)$. Under what conditions on $f$ does it follow that $g=\Theta(h)$? For instance, it ...
1
vote
0answers
43 views

Asymptotic growth over an interval

Given a function $f(x)$, we can define the new function $$ A_f(t) = \limsup\limits_{x\to\infty}\ (f(x+t) - f(x)) $$ Is there a place that this transformation has been studied? Also, given a positive ...
1
vote
1answer
217 views

Are definitions these of Big-O notation equivalent to the standard?

This definition uses hyper-reals and nonstandard analysis. Let $k^*(x)$ be the natural extension of $k(x)$. Let $f$ and $g$ be functions. $f = O(g) := \frac {f^*(H)} {g^*(H)}$ is finite for all ...
1
vote
1answer
312 views

Showing uniform convergence in probability

Suppose you want to show $sup_{x\in D}|f_n(x)|\to_p 0$, for $n\to \infty$, where $D\subset \mathbb R$ is a compact interval, $f$ is continuous depending on one or more random variables, and $\to_p$ ...
3
votes
1answer
107 views

Behavior of $\Gamma(z)$ as $\text{Im} (z) \to \pm \infty$

In a paper I'm reading it states that $\displaystyle |\Gamma(z)| = |\Gamma(a+ib)| \sim \sqrt{2 \pi} |b|^{a-\frac{1}{2}} e^{-|b|\frac{\pi}{2}}$ as $\displaystyle|b| \to \infty$. How is that derived ...
3
votes
2answers
160 views

Prove or disprove: $\sum\limits_{i=1}^n i^2 = O(n^2) $

Prove or disprove: $$\sum_{i=1}^n i^2 = O(n^2) $$ If we want to prove this, find some summation that we know the $ O(n)$ runtime for, and is $ O(n^2) $ or smaller. Otherwise, we could disprove ...
5
votes
1answer
180 views

Chain rule proof

Let $a \in E \subset R^n, E \mbox{ open}, f: E \to R^m, f(E) \subset U \subset R^m, U \mbox{ open}, g: U \to R^l, F:= g \circ f.$ If $f$ is differentiable in $a$ and $g$ differentiable in ...
6
votes
3answers
101 views

Does $n n^{1/n} =O(n)$?

I was asked does $n n^{1/n} =O(n)$ ? I can see that the left hand side is always bigger than $n$ but how would you prove the equality is false?
1
vote
1answer
239 views

Exponential decay of Heat equation solution

I'm refereeing a paper and the authors go to great lengths to prove the following fact. Let $W(t,x)$ be the solution to the linear heat equation on the half-line: $\partial_t W = D \partial_{xx} W $, ...
2
votes
1answer
65 views

simplifying an asymptotic expression

I have this expression in a statistics book, namely $nh(f(x) +o(1)+O_p(1/\sqrt{nh}))$. Where $f$ is a density function. Now, this expression is equal to $nhf(x)\{1+o_p(1)\}$. Note, that $n\to ...