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
1answer
740 views

About the asymptotic formula of Bessel function

For $ \nu \in \Bbb R$, I want to prove the well-known formula $$ J_\nu (x) \sim \sqrt{\frac{2}{\pi x}} \cos \left( x - \frac{2 \nu +1}{4} \pi \right) + O \left( \frac{1}{x^{3/2}} \right) \;\;\;\;(x ...
3
votes
6answers
524 views

Proof by contradiction that $n!$ is not $O(2^n)$

I am having issues with this proof: Prove by contradiction that $n! \ne O(2^n)$. From what I understand, we are supposed to use a previous proof (which successfully proved that $2^n = O(n!)$) to find ...
0
votes
1answer
66 views

Decay for the tail of a series.

Let $p>1$. I would like to have an estimate for the decay of the sequence $s_{n}=\sum_{k=n}^{\infty}k^{-p}$. Does anyone know of a bound of this type in the literature? Thanks!
0
votes
0answers
44 views

understanding of 1-unconditionality

Let $X=(X, \|\cdot\|_X)$ be normed space with $x_1, \ldots, x_m\in X$. Assume, $\int_{[-1,1]^m}\|\sum_{i=1}^ma_ix_i\|_Xd\mu(a)=1$, where $\mu$ is the Lebesgue measure on $[-1,1]^m$, $a \in [-1,1]^m$. ...
0
votes
1answer
129 views

How to compare big numbers that are outcome of different functions.

How is the best way to compare big numbers? They are result of two functions with different asymptotic growth. For example: Googleplex which is $10^{{10}^{100}}$ to $1000!$
3
votes
0answers
57 views

Is there a common name for $O(x^{cx})$ type functions?

Is there a common name for the growth rate of functions that are asymptotically on the order of $x^{cx}$, for some $c$? The term super-exponential is much too general. The factorial function grows in ...
1
vote
2answers
104 views

Formally prove/disprove that $\sqrt{n}o(\sqrt{n}) = o(n)$

I'm wondering how to formally show that $\sqrt{n}o(\sqrt{n}) = o(n)$. The problem I'm having is that I don't really know how to formally resolve the multiplication on the LHS. It would be ...
2
votes
3answers
131 views

Show that $(x+1+O(x^{-1}))^x = ex^x + O(x^{x-1})$ for $x\rightarrow \infty$

So I'm trying to show that for $x\rightarrow \infty$: $$(x+1+O(x^{-1}))^x = ex^x + O(x^{x-1})$$ So these complicated big-Oh expressions are clearly going to be a recurring theme in my book, and I ...
3
votes
2answers
129 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 ...
2
votes
1answer
63 views

Interpretation of $f(n) \in o(n)$

Suppose that some function $f(n)$ is in $o(n)$. Is it fomally correct to say that there exists an $N$ such that for all $n \ge N$ it holds that $$f(n) \le \frac{c n}{g(n)}$$ where $c>0$ is a ...
1
vote
1answer
62 views

Minimizers of an expression with little O notation

Suppose that $f(x) = o(\sqrt{x})$ as $x\rightarrow\infty$ and let $x^*(a)$ denote the minimizer of $f(x) + a^{3/2}/x$, that is, the value of $x$ that minimizes said expression (assuming such a value ...
6
votes
1answer
3k views

Find a big-O estimate for $f(n)=2f(\sqrt{n})+\log n$

While self-studying Discrete Mathematics, I found the following question in the book "Discrete Mathematics and Its Applications" from Rosen: Suppose the function $f$ satisfies the recurrence ...
3
votes
1answer
221 views

Asymptotics of an expression of the root of a polynomial

Given that $x_0$ is the unique positive solution of $(2-x)^{n+1}=x(x+1)\cdots(x+n)$, try to find the asymptotic value of $$ M=\prod_{k=0}^n\left(\frac{k+2}{k+x_0}\right)^{k+2} $$ with absolute error ...
1
vote
2answers
175 views

Singular Perturbation Problem? Asymptotics?

I am in the midst of solving this equation $\epsilon \ddot{y}+\dot{y}+1-\frac{1}{(y+1)^{2}}=0$ with the boundary condition $y(0)=1$ and $\dot{y}(0)=-1$ and $\epsilon$ is small. To start off with, I ...
2
votes
0answers
76 views

Two terms approximation of a recurrence [closed]

Find an approximation up to the second term of $z_n$ where $z_{n+2}=z_{n+1}+\sqrt{n}z_{n}$ and $z_{2}=2z_{1}>0$.
0
votes
2answers
79 views

Asymptotic Expansion

I was trying to solve and ODE and while doing some asymptotics, I bumped into something like this $\left(1+\frac{\gamma}{z_{0}}+\epsilon \frac{z_{1}}{z_{0}}\right)^{-2}$ where $\gamma$ $\,$ is of ...
1
vote
4answers
161 views

Estimate on an oscillatory integral

During my research I ran into the following type of an oscillatory integral, for some values of nonzero reals $a,b$: $f(R):=\int_{0}^{R} e^{2 \pi i (ar^2 + br)} dr$ and I am interested in finding a ...
0
votes
0answers
168 views

Approximations for the number of divisors of an integer

Given an integer $n$, I want to know the asymptotic order of: a. the number of distinct prime factors b. the number of non-distinct prime factors c. the number of distinct divisors d. the number ...
9
votes
1answer
1k views

How does a harmonic oscillator with nonlinear damping behave?

It is well known that for a harmonic oscillator with linear damping, $$\ddot x+c\dot x+x=0$$ with positive $c$, the amplitude of the oscillations decays exponentially when $c<2$. If it is higher ...
1
vote
1answer
104 views

Prove that $\log \log y = \mathcal{o}(\log y) + \mathcal{O}(1)$.

I just wanted some help to prove that $$\log_2 \log_2 y = \mathcal{o}(\log_2 y) + \mathcal{O}(1),$$ when $y = f(n) \in \mathcal{O}(n)$ and $y > 4$. Thanks!
0
votes
2answers
63 views

Integral of $1/x$ times a decaying function

Let $f:[1,\infty)\to\mathbb{R}$ be a measurable function with $\lim_{t\to\infty} f(t)=0$. I want to show that the function $x\mapsto \int_1^x \frac{f(t)}{t} dt$ is asymptotically sublogarithmic, i.e. ...
2
votes
2answers
250 views

Asymptotics of the solution of $x^x=n$

I need to find asymptotics of the solution of the equation $$ x^x=n $$ while $n\to\infty$. The only thing I understand is this solution grows very slowly. I can't find $x$ explicitly, I think this is ...
1
vote
0answers
40 views

if I get the asymptotic solution of a certain equation involving $ f(x)$ does it mean that the solution exists

Let's take a complicated functional equation $ f(g(x))=f(1-x)g(x) $. Let us suppose that by using a) Analytic method b) Numerical method I can prove that for example $ f(x) \sim x $ as $ ...
0
votes
1answer
106 views

Problem with this Big $O$ proof

I've been reading the wikipedia article about $Big O$ notation: http://en.wikipedia.org/wiki/Big_O_notation#Example, and i'm not sure about the second step in wich $6x^4 + |2x^3|+5$ turns into ...
2
votes
1answer
296 views

Why is $\pi$ the Limit of the Absolute Value of the Prime $\zeta$ Function?

Motivation: I was looking at the approximation of the truncated Prime $\zeta$ function $$ P_x(s)=\sum_{p\leq x}p^{-s}= \mathrm{li}(x^{1-s}) + O \left(\cdot \right) $$ (to be found here with or ...
1
vote
2answers
86 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$? ...
4
votes
1answer
231 views

Asymptotics for Bell number

Concrete Mathematics EXERCISE 9.46 Show that the Bell number $\varpi_n=e^{-1}\sum_{k\ge0}k^n/k!$ of exercise 7.15 is asymptotically equal to \[ m(n)^ne^{m(n)-n-1/2}/\sqrt{\ln n} \] where ...
3
votes
0answers
387 views

Asymptotics for the expected length of the longest streak of heads.

As Introduction to Algorithms (CLRS) describes, the problem is Suppose you flip a fair coin $n$ times. What is the longest streak of consecutive heads that you expect to see? The book claims ...
4
votes
3answers
139 views

Equivalent of $ I_{n}=\int_0^1 \frac{x^n \ln x}{x-1}\mathrm dx, n\rightarrow \infty$

I would like to show that $$ I_{n}=\int_0^1 \frac{x^n \ln x}{x-1}\mathrm dx \sim_{n\rightarrow \infty} \frac{1}{n}$$ Using the change of variable $u=x^n$: $$ I_{n}=\frac{1}{n^2} \int_0^1 ...
4
votes
2answers
355 views

Big Oh notation Question in calculus

In my text book, they state the following: $$\begin{align*}f(x) &= (\frac{1}{x} + \frac{1}{2}) (x-\frac{1}{2}x^2+\frac{1}{3}x^3+O(x^4))-1& ,x \rightarrow 0\\&= ...
3
votes
1answer
203 views

Series about Euler-Maclaurin formula

The Euler-Maclaurin formula says (from Concrete Mathematics section 9.5) \[ \sum_{a\le{}k< b}f(k)=\int_a^bf(x)dx+\left.\sum_{k=1}^m\frac{B_k}{k!}f^{(k-1)}(x)\right|_a^b+R_m \] where ...
2
votes
1answer
73 views

How to formally justify that $\int o(x) \, dx\sim o(x^2)$?

I'm trying to evaluate the following limit: $$\lim_{x\to 0}\frac{\sin\left(\int_{x^3}^{x^2}\Bigg(\int_0^t g(s^2) \, ds\right) \, dt\Bigg)}{x^8}$$ for $g:[-1,1]\to\mathbb{R}$ differentiable function ...
7
votes
1answer
282 views

Asymptotics for sum of binomial coefficients from Concrete Mathematics

Concrete Mathematics EXERCISE 9.25: Supposing \[ S_n = \sum_{k=0}^n \binom{3n}k \] Prove that \[ S_n = \binom{3n}{n}\left(2-\frac4n+O\left(\frac1{n^2}\right)\right) \] This sequence also ...
3
votes
2answers
359 views

Solution of $T(n)=2T(n/2) + n\log(\log n)$

I am struggling to solve this equation: $$T(n)=2T(n/2) + n\log(\log n).$$ I concluded that the Master Theorem does not apply in this situation so I tried to successively substitute the terms in order ...
4
votes
3answers
167 views

Equivalent of $ u_{n}=\sum_{k=1}^n (-1)^k\sqrt{k}$

I'm trying to show that $$ u_{n}=\sum_{k=1}^n (-1)^k\sqrt{k}\sim_{n\rightarrow \infty} (-1)^n\frac{\sqrt{n}}{2}$$ when $n\rightarrow\infty$ How can I first show that $$u_{2n}\sim_{n\rightarrow ...
1
vote
0answers
32 views

Asymptotic order of some sums with the Fourier coefficients

Given $f\in C^{w}[0,1]$ with periodic conditions $f(0)^{(j)}=f(1)^{(j)},\ j=0,\dots, w-1$ and its Fourier series are $f(x)=\sum_{l}f_{i}\exp(2\pi ix)$. I need to find the asymptotic order of errors ...
17
votes
2answers
726 views

A (non-artificial) example of a ring without maximal ideals

As a brief overview of the below, I am asking for: An example of a ring with no maximal ideals that is not a zero ring. A proof (or counterexample) that $R:=C_0(\mathbb{R})/C_c(\mathbb{R})$ is a ...
0
votes
1answer
146 views

Simple clarification - deduction using big-O notation

A set of lecture notes I'm reading on Halasz's theorem makes the following statement in a proof, which I can't quite follow - I was hoping someone might be able to clear up what I'm missing: ...
2
votes
1answer
247 views

Asymptotic Analysis of trignometric functions

I am new to Asymptotic analysis so please bear with me and i apologize if the following question is not well formed or is trivial. I am trying to figure out Asymptotic behavior of the following two ...
4
votes
2answers
151 views

Asymptotics of the sum $1-2^x+3^x-4^x+\cdots+x^x$

What is the asymptotics of $1-2^x+3^x-4^x+\cdots+x^x$ as $x$ becomes big? $x$ is odd only
4
votes
1answer
104 views

Numbers of the form $a^m-b^n$

Can all positive integers $k$, be written as a difference of two perfect powers $k=a^m-b^n$, with $m,n>1$ and $a,b$ positive integers? A number is imperfect if it can not, which numbers are ...
7
votes
2answers
146 views

Equivalent of $\int_0^{\infty} \frac{\mathrm dx}{(1+x^3)^n},n\rightarrow\infty$

According to my calculations $$ \int_0^\infty \frac{\mathrm dx}{(1+x^3)^n}=\frac{(3n-4)\times(3n-7)\times\cdots\times5\times2}{3^{n+1/2}(n-1)!}2\pi$$ How can an equivalent of $$ \int_0^\infty ...
1
vote
2answers
183 views

expressing $x^3 /1000 - 100x^2 - 100x + 3$ in big theta

Hello can somebody help me in expressing $x^3/1000 - 100x^2 - 100x + 3$ in big theta notation. It looks like of $x^3$ to me, but obviously at $x =0$ obviously this polynomial gives a value of $3$. And ...
0
votes
1answer
106 views

Equivalent of $ u_{n}=\int_0^{\pi/2} \cos\left(\frac{\pi}{2}\sin(x)\right)^n \mathrm dx $

I would like to find an equivalent of the sequence $u_{n}$ where $$ u_{n}=\int_0^{\pi/2} \cos\left(\frac{\pi}{2}\sin(x)\right)^n \mathrm dx $$ The substitution $x\rightarrow \frac{\pi}{2}\sin(x)$ ...
0
votes
1answer
338 views

Correct usage of asymptotic notation

Suppose that initially I have $c n$ objects, for some constant $c \in O(1)$, and I have a function $f$ that yields $f(k) = \varepsilon k$, (for $\varepsilon<1$), if $k \in \Omega(\log n)$, ...
2
votes
1answer
125 views

Asymptotic Analysis of coefficients of $\mathrm{e}^{x+x^2/2}$

Let $a_n=[x^n]\mathrm{e}^{x+x^2/2}.$ How does one show that $$ a_n \sim\frac{1}{2\sqrt{\pi}} n^{-(n+1)/2}\mathrm{e}^{-n/2+\sqrt n -1/4}?$$ I'd also appreciate references illustrating relevant ...
2
votes
1answer
79 views

Finding the asymptotic limit of an integral.

I'm having trouble finding the asymptotic of the integral $$ \int^{1}_{0} \ln^\lambda \frac{1}{x} dx$$ as $\lambda \rightarrow + \infty$. Can anyone help? Thank you!
2
votes
0answers
95 views

Asymptotic expansion of $x_{n}$, $x_{n}=\frac{1}{\tan(x_{n})}$

I would like to find a two-term or a three-term asymptotic expansion of $x_{n}$ the unique solution of $$x_{n}=\frac{1}{\tan(x_{n})}$$ on the interval $]n\pi,n\pi+\pi[ $ We have: $$ ...
2
votes
0answers
59 views

gamma funtion and estimates-typo or mistake?

In one of the lecture notes I've found that $C_n$ $$ C_n= \begin{cases} \frac{n!}{\sqrt 2 \Gamma((n/2+1)}\pi^{-1/42^{-n/2}(n!)^{-1/2}} & n\text{ even} \\[4mm] \frac{2(n!)}{(\sqrt2n+1/(\sqrt2 ...
3
votes
1answer
178 views

Solving perturbed polynomial equations

Rather than asking the most general question possible, I will frame it in terms of what I believe is an illustrative example. Let $\epsilon>0$ be a small parameter, let $a,b>0$ and $x\in ...