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
2answers
78 views

Big-$O$ inside a log operation

I would appreciate help in understanding how: $$\log \left(\frac{1}{s - 1} - O(1)\right) = \log \left(\frac{1}{s - 1}\right) + O(1)\text{ as }s \rightarrow 1^+$$ I thought of perhaps a Taylor series ...
1
vote
0answers
111 views

how many ways to make change, asymptotics

This is a simplified coin-changing question. Suppose the only coins available are all powers of $10$ dollars. How many ways are there to make change for $\$ 1000000$? In general, to make change for ...
10
votes
3answers
285 views

Closed form of $\sum\limits_{i=1}^n k^{1/i}$ or asymptotic equivalent when $n\to\infty$

Is there a "closed form" for $\displaystyle S_n=\sum_{i=1}^n k^{1/i}$ ? (I don't think so) If not, can we find a function that is asymptotically equivalent to $S_n$ as $n\to\infty$ ?
56
votes
1answer
1k views

Why are asymptotically one half of the integer compositions gap-free?

Question summary The number of gap-free compositions of $n$ can already for quite small $n$ be very well approximated by the total number of compositions of $n$ divided by $2$. This question seeks ...
1
vote
2answers
1k views

Finding Big-O with Fractions

I'd want to know how I can find the lowest integer n such that f(x) is big-O($x^n$) for a) $f(x) = \frac {x^4 + x^2 + 1}{x^3 + 1}$ I've fooled around with this a bit and tried going from $\frac ...
4
votes
4answers
477 views

Determine whether $F(x)= 5x+10$ is $O(x^2)$

Please, can someone here help me to understand the Big-O notation in discrete mathematics? Determine whether $F(x)= 5x+10$ is $O(x^2)$
9
votes
3answers
134 views

Prove that $\prod_{k=1}^{\infty} \big\{(1+\frac1{k})^{k+\frac1{2}}\big/e\big\} = \dfrac{e}{\sqrt{2\pi}}$

This result, $$\prod_{k=1}^{\infty} \big\{\big(1+\frac1{k}\big)^{k+\frac1{2}}\big/e\big\} = \dfrac{e}{\sqrt{2\pi}}$$ is in a paper by Hirschhorn in the current issue of the Fibonacci Quarterly (vol. ...
1
vote
2answers
164 views

When can we exchange expectation and maximum for asymptotic results?

Motivated in the analysis of algorithms, consider the following setup. Assume we have discrete random variables $X^{(n)}_1, \dots, X^{(n)}_n$ which we can not assume to be identical or independent. ...
0
votes
1answer
320 views

Confused about a limit proof and Big O.

I gave an incorrect proof here : How can evaluate $\lim_{x\to0}\frac{\sin(x^2+\frac{1}{x})-\sin\frac{1}{x}}{x}$ I am confused as when considering the mistakes in my proof it seems the limit cannot be ...
4
votes
1answer
97 views

How can I approximate $\sum\limits_{k=4}^{\infty}\Pr(X=k)[{\Pr(X\le k)}^6 - {\Pr(X\le k-4)}^6]$ for $\lambda \to +\infty$?

$X$ is a Poisson random variable and the probability mass function is given by: $$\Pr(X = k) = e^{-\lambda}\frac{{\lambda}^k}{k!}$$ I’ve got a probability function $f(\lambda)$ $$f(\lambda) = ...
2
votes
3answers
74 views

Asymptotic behaviour of $1- \left( \frac{\Gamma(n+\frac{1}{2})}{\sqrt{n} \Gamma(n)} \right) ^2$

I know that $$\lim_{n\rightarrow \infty}\frac{\Gamma(n+\frac{1}{2})}{\sqrt{n} \Gamma(n)}=1,$$ but I'm interested in the exact behaviour of $$a_n =1- \left( \frac{\Gamma(n+\frac{1}{2})}{\sqrt{n} ...
3
votes
2answers
117 views

Order of a function related to divisors

Let $f(n)=\max(\{d(ab):\ a,b\le n\})$ where $d(m)$ is the number of divisors of $m.$ What is the order of $f$? In particular I'm looking for an asymptotic upper bound.
8
votes
2answers
275 views

Known bounds for the number of groups of a given order.

The number of nonisomorphic groups of order $n$ is usually called $\nu(n)$. I found a very good survey about the values. $\nu(n)$ is completely known absolutely up to $n=2047$, and for many other ...
4
votes
0answers
169 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
199 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
90 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
94 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
65 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
513 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
209 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
469 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
86 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
154 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
147 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
90 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
221 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
110 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
218 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
148 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
76 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
131 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
2k 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
284 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
111 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
112 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
196 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
333 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)$?