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

learn more… | top users | synonyms (1)

11
votes
3answers
365 views

The boundedness of an integral

Is there a constant $C$ which is independent of real numbers $a,b,N$, such that $$\left| {\int_{-N}^N \dfrac{e^{i(ax^2+bx)}-1}{x}dx} \right| \le C?$$
1
vote
1answer
160 views

Justifying O-estimate of Poisson's Kernel as $x$ goes to the boundary

This question stems from a step of a proof in this paper: http://www.cmap.polytechnique.fr/~ammari/papers/04AKS.pdf The question itself I didn't feel to be "research level" as it is only an ...
2
votes
1answer
85 views

Asymptotic behavior of a sequence based on a subsequence.

Let $c\in(0,1)$, $m\geq 1$ be positive integer and $\{a_{n}\}$ a decreasing sequence of positive real numbers. Suppose that $$a_{n^{m}}\leq K c^{n}n^{-m/2}, \forall n\in\mathbb{N}, $$for some ...
1
vote
1answer
647 views

How to proof $n^2+n \in \Theta(n^2)$?

It stands to reason that $n^2+n \in \Theta(n^2)$. But how can I formally proof it? I tried next way: Generalized to $$f(n)+o(f(n)) \in \Theta(f(n))$$ Separated to $$\tag{1} f(n)+o(f(n)) \in ...
4
votes
1answer
777 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
525 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
1answer
131 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
106 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
164 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
175 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
252 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
41 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
298 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
87 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
235 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
397 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 ...
5
votes
2answers
371 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
204 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
287 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
364 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
746 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
147 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
253 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
105 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
107 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
355 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
128 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!