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

learn more… | top users | synonyms (1)

0
votes
0answers
23 views

Simple question about asymptotic notation

I'm quiet new to the asymptotic world, so apology in advance if this question seems too trivial for you experts. Given $\frac{2kn2^{-k}}{E[X]}.$ As $k \sim 2\text{log}_{2} n$, the numerator is ...
11
votes
1answer
121 views

Asymptotic Behavior of a Sum with Binomial Coefficients

The Problem: Find the asymptotic behavior (with respect to $n$) of the following sum $$\sum\limits_{j = 3}^n \binom{n}{j} \frac{(j - 1)!}{2\cdot n^j}. $$ Where the Problem Comes From: If we ...
3
votes
1answer
62 views

Calulate a limit involving $\zeta{(\zeta{(z)})}$

I'm currently trying to evaluate the following limit: $$ \lambda=\lim_{z\to\infty}{\left[2^z-\left(\frac{4}{3}\right)^z-\zeta{(\zeta{(z)})}\right]} $$ A look at numerical approximations suggests, that ...
-4
votes
2answers
83 views

Find witnesses proving that $f(x) = 2x^3 + x^2 + 5$ is $O(x^3 )$. [closed]

Find witnesses proving that $f(x) = 2x^3 + x^2 + 5 \textrm{ is } \mathrm{O}(x^3 )$. What do i need to do here? Like step by step?
0
votes
0answers
41 views

For any arithmetic progression $n \in \Bbb{N} : n \equiv b \pmod a$, the natural density is $\frac{1}{a}$?

This question comes from here (page 10). Given that $d(A) := \lim_{x\to\infty}\frac{1}{x}\sharp\{n \leq x : n \in A\}$, how do I get that: 1) $d(n \equiv b \pmod a) = \lim_{x\to\infty}(\left [ ...
-2
votes
0answers
50 views

BIG OH:$ f (x) = 3x^3 + 2x + 4$. One has

I have this question in my homework. Its an a multiple choice question and goes as following: Let $f (x) = 3x^3 + 2x + 4$. One has that $O(x^3)$ ** the answers have been checked with the teachers ...
0
votes
0answers
29 views

How to prove $x^m = O(e^x)$ for any $m \gt 0$?

My attempt: It's true for $m = 1$ clearly. Now assume true for $m=1\dots M-1$. Then $x = O(e^x)$ and $x^{M-1} = O(e^{M-1})$. Lemma: if $f = O(g)$ and $f' = O(g')$ then $ff' = O(gg')$. Proof: $f = ...
1
vote
2answers
31 views

Simple question, what is meant by 'as $x \to \infty$ the number of squares $\leq x$ is $\sqrt{x} + O(1)$?

For $x \to \infty$: the number of squares $n^2 \leq x$ is $\sqrt{x} + O(1)$. From here (page 6). More specifically, do they mean that... I'm confused now. I'm really not sure what they mean ...
3
votes
1answer
33 views

$\sum_{n \leq x} \frac{1}{n} = \int_{1}^x \frac{dt}{t} + O(1)$ help deriving it

On page 5 of: Probabilistic Number Theory by Dr.J¨orn Steuding, there's $\sum_{n=2}^{[x]} \frac{1}{n} \lt \int_{1}^{[x]} \frac{dt}{t} \lt \sum_{n=1}^{[x] - 1}$ Therefore integration yields: ...
1
vote
1answer
124 views

Can Cauchy theorem be applied to $\log{(z)}e^{ixz}$?

I'm reading about asymptotic analysis on the integral $I(x)=\int_0^1{\ln{t}e^{ixt}}dt$. The book tells me that I can use Cauchy theorem to deform the contour into a rectangular contour: $0 \to iT \to ...
0
votes
0answers
24 views

The function $g(x)$ is in $\Omega(x^c)$ as $x\rightarrow 0$ for all $c>0$. Does this imply that $\lim \inf_{x\rightarrow 0} g(x) > 0$?

Consider a function $g: \: \mathbb R^+ \mapsto \mathbb R^+ $. For any $c>0$ this function is in $\Omega(x^c)$ as $x\rightarrow 0$. That is, given $c>0$ there exist $L$ and $x_0$ such that $g(x) ...
3
votes
1answer
908 views

Little 'o' / Big 'O' Definitions

I understand, or at least think I understand, the nature of a function that is "little o": If $f$ is a function between Banach spaces E and F, then it is "little-o" if $$|x|\rightarrow 0 \implies ...
5
votes
3answers
9k views

Family of functions with two horizontal asymptotes

I'm looking for the equation of a family of functions that roughly resembles the sketch below (with apologies for the crudeness of said sketch):     Properties I'm looking for: ...
7
votes
0answers
98 views

Bear of an integral

I have a pretty ferocious integral to solve, and would be over the moon if I were able to get some sort of analytic expression / insight for it. $$ I = \int_{r}^{\infty} r_0^{-5/2} W_{-i\alpha'/2, ...
10
votes
1answer
76 views

Asymptotic behaviour of log log sum

I am interested in the asymptotics of $$F(m) := \prod_{j=1}^m \log(j+1) = \exp\left(\sum_{j=1}^m \log \log(j+1) \right)$$ Is there anything known? If not I figure I will need some good bounds on the ...
1
vote
1answer
54 views

Asymptotic for $\int_{\mathbb{R}}e^{ik(sin x - x)}f(x)\, dx$

Suppose $f$ is a smooth compactly supported function supported in $[-\pi, \pi]$. The problem I am working on is to show that $$\int_{\mathbb{R}}e^{ik(\sin x - x)}f(x)\, dx = ...
2
votes
1answer
66 views

Upper bounding a tricky sum

For a problem in probability, I'm trying to find an upper bound for $$ \sum_{d=0}^k\binom{k}{d}\gamma^d(1-\gamma)^{k-d}\left(1-p^d(1-p)^{k-d}\right)^m$$ which will help me analyze what values of ...
0
votes
2answers
29 views

Prove or disprove the following asymptotic relations

$P(x) = 2^x$ Prove or disprove that $p(n^3 + 4) \in O\left(p\left(n^3\right)\right)$ $2^{(n^3 + 4)} \in O(2^{n^3})$ $\lim_{n \rightarrow \infty} \space \frac{2^{n^3 + 4}}{2^{n^3}}$ using ...
9
votes
1answer
99 views

An upper bound for Summative Fission numbers

I recently found OEIS entry A256504 and have been playing around with this sequence a bit. Its definition is: For a positive integer $n$, find the greatest number of consecutive positive integers ...
0
votes
1answer
318 views

How can I tell/compare the asymptotic complexity of a function?

For something, like a quadratic I just take the highest degree and see if it is theta or big O or Omega of n, correct? So like 2n^2+2n+1 could be theta(n^2). What are the general ...
1
vote
1answer
39 views

Is this a correct proof that $\tau(n)$ is eventually smaller than any $n^{\delta}$, $\delta>0$?

Is this a correct proof that $\tau(n)$ is eventually smaller than any $n^{\delta}$, $\delta>0$? I'm not even sure about the statement, let alone the proof. Let's first proof this result: $\tau(n) ...
0
votes
1answer
47 views

How to prove that $\left(\log \log n\right) \times \left(\log \log \log n\right) = Ω\left(\log n\right)$

Is $$\log \log n \times \log \log \log n = \Omega(\log n) $$ How can we prove it. Actually I'm trying to prove that $f(n) = \lceil(\log \log n)\rceil !$ is polynomially bounded. It means $$c_1 ...
2
votes
1answer
52 views

Recurrence equation approximation

I have the following recurrence relation, $$x_{i+1}=a\cdot x_i^{\frac{2-2\alpha}{3}}+x_i,$$ where $a>0, \alpha>0$, and $x_0>0$. My goal is to get an approximate the expression for $x_i$. I ...
8
votes
1answer
219 views

Mean Value of a Multiplicative Function close to $n$ in Terms of the Zeta Function

Let $f(n)$ be a multiplicative function defined by $f(p^a)=p^{a-1}(p+1)$, where $p$ is a prime number. How could I obtain a formula for $$\sum_{n\leq x} f(n)$$ with error term $O(x\log{x})$ and ...
0
votes
0answers
19 views

Asymptotic form of Whittaker function

I am working with Whittaker functions for a project and have no experience with asymptotic analysis - how is the following expression, for $\kappa \rightarrow \infty$ through the real numbers ...
2
votes
2answers
48 views

Asymptotic Estimates for a Strange Sequence

Let $a_0=1$. For each positive integer $i$, let $a_i=a_{i-1}+b_i$, where $b_i$ is the smallest element of the set $\{a_0,a_1,\ldots,a_{i-1}\}$ that is at least $i$. The sequence ...
9
votes
2answers
216 views

Fourier transform of $\Gamma \left (\frac{1}{2}-i \frac{p}{2 \pi} \right) /\sqrt{ \cosh(p/2)}$

Is it possible to compute the following Fourier transform analytically? $$\psi(x) = \frac{1}{\sqrt{4 \pi}}\int \Gamma \left (\frac{1}{2}-i \frac{p}{2 \pi} \right) \frac{e^{i p x}}{\sqrt{ \cosh(p/2)}} ...
4
votes
1answer
72 views

Average order of $\mathrm{rad}(n)$

Let $\mathrm{rad}(n)$ denote the radical of an integer $n$, which is the product of the distinct prime numbers dividing n. Or equivalently, $$\mathrm{rad}(n)=\prod_{\scriptstyle p\mid n\atop p\text{ ...
4
votes
1answer
71 views

Evaluating a function in a closed form

Let $$g(x)=\lim_{n\rightarrow\infty}\sqrt{n}\int_0^x z^2e^{n(\cos^2z-1)}\ \mathsf dz$$ Evaluate $g$ in closed form. The answer is right here: ...
0
votes
1answer
47 views

Boundary layer problem

This question is taken from Bender & Orszag "perturbation methods" $y' = (1 + X^{-2}/100)y^2 - 2y + 1$ ,$y(1)=1$ first we can see that if we set $\epsilon=100x^{2}$ we can translate the above to ...
0
votes
3answers
58 views

How to prove or disprove $n^{28} = O(2^n)$

Prove or disprove $n^{28} = O(2^n)$. My solution: $$\lim _{n \to \infty} \dfrac {2^n} {n^{28}} = \dfrac {2*2*2 \dots _{(n \ times)}} {n * n * \dots _{(28 \ times)}}$$ As $n \to \infty$, both the ...
2
votes
2answers
57 views

Growth Rate $n\ln n$

I mistakenly posted this on MathOverflow. I hope this is a better place for it. I have been investigating a problem about sports teams and came across the function $n\ln(n)$. I want to see if I can ...
0
votes
1answer
29 views

Proving the asymptotic relationship between two functions

I was playing around with numbers a few days ago and found an asymptotic approximation to two functions: $$y=-\ln{x}$$ And $$y=x^{1-\frac{1}{x}}-x$$ Can I have a proof that it is (or isn't) ...
0
votes
1answer
26 views

What can we say about the distribution of the prime-power factors of a big factor-rich number?

Let us say that a positive integer is factor-rich if it has more factors than any smaller integer. For example, $60$, which has twelve factors, is factor-rich; and therefore $72$, which also has ...
0
votes
1answer
58 views

Limit of Quotient of two functions changed by constant amount

Let $f(x), g(x)$ be two function's, how to show that $$ \limsup_{x\to a} \frac{f(x)}{g(x)} = \limsup_{x\to a} \frac{f(x)}{g(x) + c} $$ for $a \in \mathbb R \cup \{ \pm \infty \}$ and $c \in \mathbb ...
0
votes
0answers
13 views

Proving that an asymptotic series is uniform for parameter belonging to a compact subset of the parameter space.

Let $U$ be a disk centered at $z=1$ of radius $\delta$. Given the function $h(z)=\frac{1+i(z^2-1)^{1/2}\sin(\alpha/2)}{1-i(z^2-1)^{1/2}\sin(\alpha/2)}$, define the function $$w(z)=\frac{1}{2}\ln h(z) ...
2
votes
1answer
44 views

Alternative geometric interpretation for big-o and little-o

I understand that, in big-o notation, when we say that a function $f$ is $O(x^2)$ we're basically saying that $$|f(x)|\le M |x^2|$$ for some constant $M>0$ and for all $x>x_0$ for some ...
3
votes
1answer
51 views

What does this use of little-o notation mean?

I am currently going through the proof of Prime Number Theorem, as given in Hardy and Wright, and in it they define the following constant: $$\alpha = \limsup_\limits{x \to \infty} \left|V(x) ...
8
votes
1answer
143 views

Does $a_0=0, a_1=1, a_{n+2}=2a_{n+1}-3a_n$ ever return to 1 or -1 for $n>3$?

The sequence in question is the Lucas or Generalized Fibonacci sequence A088137. It's easy to write down its generating function $\frac{x}{1-2x+3x^2}$ and an explicit formula $a_n = ...
3
votes
1answer
186 views

Asymptotic behavior of the minimum eigenvalue of a certain Gram matrix with linear independence

Consider the density matrices with the following spectral decompositions: $$\rho=\lambda_1|\nu_1\rangle+\lambda_{2}|\nu_2\rangle$$ and $$\sigma=\gamma_1|\omega_1\rangle+\gamma_2|\omega_2\rangle$$ such ...
1
vote
0answers
38 views

Compare growth of function and derivative

Suppose $f:\mathbb R \rightarrow \mathbb R$, $O(1)<f(x)<O(x)$ (i.e. has slower than linear growth but is unbounded), $\lim_{x\rightarrow \infty} f'(x)=0$ and $f'$ is monotonic. Is it possible to ...
1
vote
1answer
18 views

Compare growth of function and its derivative.

Suppose $f:\mathbb R \rightarrow \mathbb R$, $f(x)<O(x)$ (i.e. has slower than linear growth), $\lim_{x\rightarrow \infty} f'(x)=0$. Is it possible to show that there exists a $\delta$ such that ...
3
votes
3answers
93 views

How do I show that as $z \to \infty$ that $\int_0^\infty \frac{t - \lfloor t \rfloor - 1/2}{z + t} dt = O(z^{-1} )$??

How do I show that as $z \to \infty$ we have $$ \int_0^\infty \frac{t - \lfloor t \rfloor - 1/2}{z + t} \,dt = O(z^{-1} )? $$ According to Serge Lang, the integral on the left is the error term for ...
6
votes
4answers
103 views

Which of $\log{\sqrt{n\log{n}}}$ and $\sqrt{\log{n}}$ grows faster?

Which of the following functions grows faster: $\log{\sqrt{n\log{n}}}$ or $\sqrt{\log{n}}$? I feel the second one should be the answer, but I find it difficult to prove as the derivatives get very ...
2
votes
1answer
140 views

Mysterious subleading corrections to sums with internal dependence on limit

Is there a standard method for finding expansions in $N$ of sums like $$S(N)=\sum_{n=0}^N \sqrt{N^2-n^2}$$ beyond the first term? It is easy to compute here that $$S(N)=N^2 \int_0 ^1 \sqrt{1-x^2} ...
1
vote
1answer
76 views

Asymptotic expansion of integral with hyperbolic functions

Consider the integral given by $$f(r)=\int_{0}^{\tanh(r)} \arccos\left(\frac{\sigma}{\sinh(r)\sqrt{1-\sigma^2}}\right)\cdot \frac{1}{\sqrt{\sigma^2+a^2}}d\sigma,$$ where $a>0$. I am wondering ...
1
vote
0answers
16 views

Central Limit Theorem for asymptotically i.i.d. random variables

I have a ergodic stationary sample of independent column random vectors $\{\mathbf x_1, \ldots,\mathbf x_n\} \equiv \mathbf X_n$, $\mathbf x_i \in \mathbb R^k$, with finite moments and cross-moments. ...
2
votes
1answer
54 views

Poisson distribution Tail

Assume that for each $n$, $X_n$ has a Poisson distribution with mean $\lambda_n = \sqrt{n\log{n}}$. We want to prove that $$\lim_{n\rightarrow\infty} 1 - \sum_{i=0}^{\lfloor\sqrt{n}\rfloor} Pr(X_n=i) ...
2
votes
1answer
46 views

Upper bound for $|\zeta'(s)|$ near the line $\sigma=1$, a detailed proof

In page 285 Apostol leaves as a reader's asigment the proof that $|\zeta'(s)|=O(\log^{2}t)$, this is for every $T>0$ there exists a positive constant $K$ (depending on T) such that ...
1
vote
2answers
65 views

Does this number blow up or go to zero?

$2\pi \epsilon^{3}(\log(\epsilon)+2\pi)^2$ Let $\epsilon \to 0$. I believe $2\pi \epsilon^{3}(\log(\epsilon)+2\pi)^2 \to 0$, and there is no concern about the blow-up of log at the origin. But can ...