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
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
276 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
723 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
145 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
335 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
94 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
177 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 ...
1
vote
1answer
39 views

Hyperbolic sine and landau notation

I have given a function $f$: $$ f = \begin{pmatrix} \sinh(x_1 x_2) \\ \cosh(x_1 x_2) \end{pmatrix} $$ We have to show that this is possible: $$ f = \begin{pmatrix} 2x_1 x_2 \\ 1 \end{pmatrix} + ...
0
votes
1answer
158 views

How to formally prove that $f(n)=\Theta f(n+1)$

How to formally prove that $f(n)=\Theta f(n+1)$? It's supposed to be easy, but I still can't get it. Thank you very much.
-1
votes
3answers
2k views

What is the upper bound on $T(n) = 3T(n/2) + n$?

The upper bound on $T(n) = 3T(n/2) + n$ is: $O(n \lg n)$ $O(n \lg 3)$ $O(n^2)$ $O(n \lg n + n)$
8
votes
1answer
134 views

Comparing average values of an arithmetic function

Suppose $f(n)$ is a positive real-valued arithmetic function such that $$ \frac1n\sum_{k=1}^nf(k)\sim g(n) $$ for $g(x)$ a monotonic increasing function. What can be said about the asymptotic behavior ...
2
votes
1answer
139 views

Next asymptotic term of the average order of sigma

$$ \sum_{k=1}^n\sigma(k)=\frac{\pi^2}{12}n^2+O(n\log n). $$ Is the next asymptotic term known? That is, is there a monotonic increasing function $f(x)$ such that $$ ...
7
votes
3answers
4k views

Prove that $\log(n) = O(\sqrt{n})$

How to prove $\log(n) = O(\sqrt{n})$? How do I find the $c$ and the $n_0$? I understand to start, I need to find something that $\log(n)$ is smaller to, but I m having a hard time coming up with the ...
1
vote
0answers
96 views

Asymptotics of an integral

Consider an integral $$ I(x) = \int\limits_{\mathbb{R}^n} e^{i\xi x } \delta(\xi^2-k^2)\chi( (\xi-k,\gamma)) \, d\xi $$ where $x, k, \gamma \in \mathbb{R}^n$, $|\gamma| = 1$ and $(x,y)\equiv xy = ...
0
votes
1answer
542 views

Interesting Recurrence Relation $T(n) = T(\sqrt{n}) + T(n-\sqrt{n}) + n$

I found an interesting recurrence that I do not know how to solve. I think this has to do with quicksort with pivots at rank $\sqrt{n}$. I do not know how to approach this problem nor found any ...
1
vote
1answer
126 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 ...
0
votes
1answer
80 views

WKB approximation question

I was reading some stuff on asymptotic analysis, but how do you get from the 1st line to the 2nd line? $y \sim \frac{1+x}{2\lambda}\exp\left(\frac{\lambda x}{1+x}\right) - ...
2
votes
1answer
769 views

properties of a real analytic function

If there are a radius $r>0$ and constants $M,C\in\mathbb R$ for all $y\in U$ with $$|\partial^if(x)|\leq M\cdot i!\cdot C^{|i|}\space\space\space\space \forall x\in\mathbb B_r(y),i\in\mathbb ...
1
vote
1answer
967 views

Big-O notation always holds for this two functions?

For two any functions $f(n)$ and $g(n)$ always holds: $f(n) = O(g(n))$ or $g(n) = O(f(n))$ Right? Thanks
5
votes
1answer
247 views

expansion of $\int_0^\infty\left(\frac{\sin t}t\right)^p\mathrm dt$ in inverse powers of $p$

This question relates to this answer I gave to a question about the integral $$\int_0^\infty\left(\frac{\sin t}t\right)^p\mathrm dt\;.$$ I derived an expansion in inverse powers of $p$ and then ...
3
votes
1answer
300 views

Disproving a big O equation

As a homework assignment I am trying to prove/disprove the next statement: Let $f(x)=O_a(g(x))$, then $\forall A,B\in\mathbb{R}\rightarrow A\cdot f(x)=O_a(B \cdot g(x))$ Which I think is wrong ...
14
votes
3answers
422 views

Can a function “grow too fast” to be real analytic?

Does there exist a continuous function $\: f : \mathbf{R} \to \mathbf{R} \:$ such that for all real analytic functions $\: g : \mathbf{R} \to \mathbf{R} \:$, for all real numbers $x$, there exists ...
1
vote
0answers
76 views

Describe growth of $\epsilon n$

For all $\epsilon$ we have that $f(n)\le \epsilon n$ where n is a natural number. What can we say about the growth of $f(n)$? Clearly $f(n)=O(n)$, can we say anything sharper?
1
vote
1answer
504 views

Big O Notation question

I am trying to understand the Big-O and little-O notation, so I plotted 2 graphs which I have posted below, but I still dont really get the concept of it. What exactly does the ...
1
vote
0answers
51 views

Asymptotic bounds: $\ll$ vs. $\ll_{\epsilon}$?

I am feeling a bit slow today. In Analytic Number Theory it is usual to express asymptotic bounds by specifying the relation of the constant to a specific variable, i.e. $\log n \ll_\epsilon ...
0
votes
1answer
110 views

asymptotic limit of $\int_0^{\infty}\left(1-\frac{t^2}{2(2k+3)}+\frac{t^4}{2\cdot 4\cdot(2k+3)\cdot(2k+5)}\right)^qdt$

Help me please with the following integral. I've asked this question before Asymptotic limit of the integral with polynomial, but it turns out that it was incorrect question. I should get an ...
2
votes
2answers
2k views

Why is $\log(n!)$ $O(n\log n)$?

I thought that $\log(n!)$ would be $\Omega(n \log n )$, but I read somewhere that $\log(n!) = O(n\log n)$. Why?
2
votes
1answer
75 views

asymptotic limit at the integral

I would like to get an asymptotic limit at the following integral: for $p\ge 2, n \in N$, $t \ge 0$ $$ \int_{0}^{\frac 12 \sqrt{(n+1)!}}\left(1-\frac{t^2}{2^2(n+1)!}\right)^p \mathrm{d} t $$ I think ...
4
votes
1answer
126 views

With probability $o(1)$

I am not sure how to read little/big O expressions in probability theory: What does a statement like "with probability $1-o(1)$" mean? Does it mean with high probability?
8
votes
2answers
1k views

Compactly supported function whose Fourier transform decays exponentially?

It's well known now that a function can not be compactly supported both on the space side and the frequency side (so-called uncertainty principle). On the other hand a function can have exponential ...
0
votes
1answer
107 views

Explicit Big-$\mathcal{O}$ proof with predicate logic

For my newest homework I have given two functions $h,h^+:\mathbb{N}\to\mathbb{R}$ with $h(n)=n^{(-1)^n}$ and $h^+(n)=h(n+1)$. I have to proove that $h^+(n) \not\in\mathcal{O}(h(n))$ with an explicit ...
0
votes
1answer
99 views

Simple question about an asymptotic equality

Could someone please explain the second equality in Conjecture 1.1: http://arxiv.org/pdf/math/0501313v2.pdf ? (reproduced below) $(1+o(1))n^22^{1-n}=\left(\frac{1}{2}+o(1)\right)^n$ Initially, I ...
0
votes
2answers
1k views

big o notation / asymptotic for factorial

I want to write $g(x)=x!\cdot(x^4-1)$ in the big O notation $g\in \mathrm O(???)$ for $x\rightarrow\infty$. But I have no idea how to do this. Thanks for helping!
5
votes
2answers
819 views

Asymptotic expansion of integral involving modified Bessel-function

I would like to obtain the asymptotic expression for $\alpha \to \infty$ of the following integral $$I(\alpha)=\int_0^\infty\!dx\,x (1 - \cos[2\alpha K_0(x)]) = \int_0^\infty\!dx\, 2x \sin^2[\alpha ...
3
votes
0answers
96 views

Asymptotics of $\sum_{n=1}^{\infty}x^{n+1/n}/n!>e^x$?

Is there a way to find precise asymptotics or better bounds of series such as $\sum_{n=1}^{\infty}x^{n+1/n}/n!>e^x$ ? Or $\sum_{n=1}^{\infty}x^{\sqrt n}/e^n$?
2
votes
1answer
61 views

$f \in O(g)$, iff $\limsup_{n\to\infty}|\frac{f(n)}{g(n)}| < \infty $

Given the functions $f$, $g$: $\mathbb{N} \to \mathbb{R}$ I have to prove that, $f \in O(g)$, iff $\limsup_{n\to\infty}|\frac{f(n)}{g(n)}| < \infty $ How can I prove it formally (at best using ...
1
vote
3answers
271 views

Asymptotic formula for the logarithm of the hyperfactorial

Background: I was trying to derive an asymptotic formula for the following: $$\sum_{m\leqslant n}\sum_{k\leqslant m}(m\ \mathrm{mod}\ k),$$ which I think I succeeded in doing (I will skip some steps ...
1
vote
2answers
79 views

Simplifying a logarithm of a little-o (circuit complexity)

I have an expression which I think is $o(2^n)$, but I'm having difficulty simplifying it: $o(2^n/n)\log(o(2^n/n) + n)$ I can ignore the extra $n$ sitting at the end, since $o(2^n/n) + n = o(2^n/n + ...