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

learn more… | top users | synonyms (1)

3
votes
1answer
76 views

How to find asymptotics of integrand?

Let $ f \in C ([0, \infty)) $ be s. t. $$f(x) \int_0^x f(t)^2 dt \to 1, x \to \infty.$$ How to prove that $f(x) \sim \left( \frac 1 {3x} \right)^{1/3} $ as $x \to \infty?$
2
votes
0answers
58 views

Asymptotics and Related Properties

I have a rather general question: If there are two integer sequences such that $$\lim_{n\to\infty}A(n)/n=\lim_{n\to\infty}B(n)/n=c$$ is there anything else that can be said about them necessarily? ...
2
votes
0answers
98 views

Aymptotic analysis for Following fucntions

Below is an excercise from algorithm design manual For each pair of expressions (A,B) below, indicate whether A is O, o, Ω, ω, or Θ of B. Note that zero, one or more of these relations may hold for a ...
0
votes
1answer
102 views

Notation almost sure convergence

In an article they use a notation which I'm not familiar with and I appreciate your thoughts on this. It is about almost sure convergence. Suppose $C_i$ is a constant, $X_n$ and $Y_n$ are random ...
1
vote
1answer
83 views

Asymptotic analysis comparision for $2^n$ and $(3/2)^n$

1) $$f(n) = 2^n\,,\quad g(n) = (3/2) ^ n$$ Is $f(n) = \Theta(g(n))$? Can someone please explain this to me ? 2)$$f(n) = n^2+\log n\,,\quad g(n) = n^2$$ I know that $f(n) = \Theta(g(n))$ ...
0
votes
1answer
142 views

why does the h in Torricelli's law (the form that relates height to time) go to zero rapidly?

https://class.coursera.org/calcsing-002/lecture/320 In the the above linked lecture at 5:44, we are trying to find how fast liquid leaks from a cone shaped tank. I understand the derivation but at ...
0
votes
2answers
81 views

Is it possible for a function(f) to be $O(f)$ but not $o(f)$?

Is it possible for a function(f) to be $O(f)$ but not $o(f)$? or $o(f)$ but not $O(f)$? I guess it might be possible for a function that is not monotonically increasing. Is there an example of this ...
2
votes
1answer
201 views

Numerical Analysis best estimate on polynomial order

I need to determine the best integer value of $k$ for the equation: \begin{equation} \arctan(x) = x + O(x^k) \text{ as $x\to 0$} \end{equation} Taylor's Theorem with Lagrange Remainder would ...
2
votes
2answers
93 views

How can an oblique asymptote be $y = x$ , as $x\to \infty$?

In my Calculus book, an oblique asymptote defined as: Oblique Asymptote: the function $y = f(x)$ has an oblique asymptote $y = mx + n$, if: $$\lim_{x\to \infty} {f(x) \over x} = m$$ ...
1
vote
3answers
70 views

Numerical Analysis and Big O

How can I show that $e^x -1$ is not $O(x^2)$ as $x\to0$ I'm not sure where to start. We can use Taylor's Theorem with remainder: \begin{equation} e^x = \sum\limits_{k=0}^n\dfrac{x^n}{n!} ...
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 ...
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 ...
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$ ?
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. ...
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)$
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?
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) = ...
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 ...
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) = ...
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), ...
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.
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} ...
1
vote
1answer
149 views

How can Big-O be proved using derivatives?

Say we have: $$f(n) \in O(g(n))$$ By definition we need to show that: $$0 \le f(n) \le c\cdot g(n) $$ for some $c>0$ and for all $n>n_0$. This is usually not difficult when rational and ...
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 ...
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 ...
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$ ?
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 ...
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
120 views

Can a discrete function have an asymptote?

I have this function which approaches zero in discrete steps: $$\frac{1}{2^{int(x)}}$$ My question is that although this function shows asymptotic behaviour in that it approaches $$y=0$$ does it ...
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$ ...
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 ...
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.
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}$$ ...
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 ...
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 ...
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 ...
9
votes
1answer
271 views

What is a good asymptotic for $f_n = f_{n-1}+\ln(f_{n-1})$?

Let $f_0=2$ and $f_n=f_{n-1}+\ln(f_{n-1})$. What is a good asymptotic to the sequence $f_n$? With good I mean much better than $f_n \sim \dfrac{3n \ln(2)\ln(n)}{2}$.
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 ...
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
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 ...