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

learn more… | top users | synonyms (1)

1
vote
1answer
48 views

On corollary and theorem involving autonomous 1st-order ODEs

Suppose we have an autonomous first-order ordinary differential equation $$\frac{dx}{dt} = f(x) \tag{*}$$ where $f$ is continuously differentiable for all $x \in D \subseteq \mathbb R$ s.t. the ODE ...
0
votes
1answer
37 views

On “bounded” in intuition for a theorem involving autonomous 1st-order ODEs

Suppose we have an autonomous first-order ordinary differential equation $$\frac{dx}{dt} = f(x) \tag{*}$$ where $f$ is continuously differentiable for all $x \in D \subseteq \mathbb R$ s.t. the ODE ...
1
vote
0answers
39 views

Help on Big O proof

I need some help with a big O proof. I think I have a proof but I feel like some of the steps aren't logically compatible. The Question: For all functions f,g with domain $\mathbb{N}$ that maps to $\...
0
votes
2answers
54 views

Function with an asymptote at y=-1 and y=1

I'm looking for a function that has two asymptotes parallel to the x-axis. Preferably it should also only cross the x-axis at (0,0) and be built without using any trigonometric functions. Mind you, if ...
0
votes
1answer
24 views

Lower bound on binomial coefficient

Prove that $\binom{n}{k} ≥ \left(\frac{n}{k}\right)^k$ for integers $0<k<n $. I used Stirling formula to find the the combination of the left part but it goes very long and I can not find and ...
0
votes
0answers
32 views

Asymptotic to $f^{-1}(f ' (x)) $?

Let $tr(n)$ be the triangular numbers and $te(n)$ be the tetrahedral numbers. $$g(x) := \sum \frac{x^n}{n! 2^{tr(n)}}$$ $g'(x) = g(\frac{x}{2}) $ Now consider the analogue $$ f(x) = \sum \frac{x^n}...
1
vote
1answer
48 views

Has limit $\frac{\sigma_0(n)\sigma_2(n)}{(\sigma(n))^2H_n},$ where $H_n$ is the nth harmonic number?

By specialization of an inequality I can write $$2 \sum_{k=1}^{n-1} \frac{1}{d_{k}} \sum_{l=k+1}^{n} \frac{1}{d_{l}}\leq 2\frac{\sigma_0(n)-1}{\sigma_0(n)}\cdot \left( \frac{\sigma(n)}{n} \right)^2, $...
1
vote
2answers
28 views

Big-O proof of inclusion

I'm working on this proof of inclusion:$$\log_2(8^n)\in{\mathcal O(n)}$$ $$\log_28^n-cn\leq0$$ for all $n>n_0$. Is there a log rule that I can use to further simplify before I plug random values to ...
0
votes
1answer
20 views

How to calculate $O(\sum_{k=1}^{K}(N-k)(k+1)^2)$?

Using the formula for the sum of the squares and the sum of first $K$ numbers I can get that: $$\sum_{k=1}^{K}(N-k)(k+1)^2=\dfrac{1}{12}K(-3K^2+2K^2(2N-7)+3K(6N-7)+26N-10)$$ Now I guess I can ...
0
votes
0answers
18 views

asymptotic expansion of an expression involving modified bessel function

I am looking for the asymptotic behavior of $$g(t,\nu)=e^{-t^2}\left[I_\nu(t^2)+\frac{1}{2}\left(I_{\nu+1}(t^2)+I_{\nu-1}(t^2)\right)\right]$$ as $t\rightarrow \infty$. Here $\nu$ only takes even ...
6
votes
1answer
113 views

Proportion of elements of prime order $p$ in $S_n$

I was trying to answer the following question recently : What is the proportion of elements of order $p$ in the symmetric group $S_n$ , where $p$ is some prime number ? I managed to work out that in ...
1
vote
1answer
50 views

What's about $\sum_{k=1}^{n-1} p_{k} \sum_{l=k+1}^{n} p_{l}$ for prime numbers?

By specialization of this formula, here in PROBLEMA 36, page 453 (in spanish), taking $\frac{1}{x_i}$ as the ith prime number we've (with at least two summands) $$ \left( \sum_{k=1}^{n} p_{k} \...
2
votes
2answers
68 views

Arrange the following:$(1.5)^n, n^{100}, (\log n)^3, \sqrt n\log n, 10^n, (n!)^2, n^{99}+n^{98}, 101^{16}$

Here is the question repeated: Arrange the following in order into increasing order of growth rates. $$(1.5)^n, n^{100}, (\log n)^3, \sqrt n\log n, 10^n, (n!)^2, n^{99}+n^{98}, 101^{16}$$ I graphed ...
1
vote
0answers
49 views

Complexity of FFT algorithms (Cooley-Tukey, Bluestein, Prime-factor)

I need to be able to explain the complexity of three Fast Fourier Transform algorithms: Cooley-Tukey's, Bluestein's and Prime-factor algorithm. Unfortunatelly, I'm a little lost in the process. ...
1
vote
1answer
23 views

Running Time Analysis

Here is the problem: sum = 0 for i = 1 to n for j = 1 to i^2 for k = 1 to j sum ++ Using three summations, $\sum_{i=1}^{n} \sum_{j=1}^{i^2} \sum_{k=...
4
votes
2answers
51 views

$\prod _{k=2}^{n} {\log k}$ is big-$O$ of what?

$$\prod _{k=2}^{n} {\log k}$$ is a big-$O$ of what? I can see it $O(n!)$ but is there a tighter solution?
2
votes
1answer
56 views

Evaluating $\lim_{x\to\infty}\frac{1}{x}\int_2^x M(t)\cdot f'(t)dt$, where $M(x)$ is Mertens functions

Let $\mu(n)$ the Möbius function. I know that combining Abel summation formula, the Prime Number Theorem and l'Hôpital's rule I can deduce $$\lim_{x\to\infty}\frac{1}{x}\sum_{2\leq n\leq x}\mu(n)\cdot\...
0
votes
1answer
36 views

Does any quadratic function in the form $an^2 + bn + c$ equal $\Theta(n^2)$ in asymptotic notation?

On a Khan Academy post (see here) about Big-$\Theta$ notation, the author attempted to convert the quadratic function $6n^2 + 100n + 300$ to asymptotic notation. They started by dropping the $n^2$ ...
1
vote
0answers
48 views

Sum of first n primes [duplicate]

Can we claim it is asymptotic to $n^2\log n$? I argue that because $p_n\sim n\log n$, we can say: $$\sum_n n\log n=\log1+2\log2+\dots+n\log n$$ $$=\log1+\log2+\dots+\log n$$ $$+\log2+\dots+\log n$$ ...
1
vote
1answer
31 views

Averaged Multinomial Coefficient

Following on from the asymptotic value of the central binomial coefficient, namely: $$\dbinom{2n}{n}\sim\dfrac{4^n}{\sqrt{\pi n}}$$ we have the multinomial coefficient: $$\dbinom{n}{k_1 k_2\dots ...
4
votes
0answers
24 views

What is known about the counting function of Gaussian primes"

The counting function of primes among $\Bbb{N}$, describing the asymptotic density of the primes, is well known (the Prime Number theorem). Let's define a mild generalization of the counting function ...
0
votes
1answer
64 views

Prove that $1^3 + 2^3 + \cdots+n^3$ is $O(n^4)$ [closed]

I suppose I am not exactly familiar with the process for finding the "Big-O" of this problem. Isn't the highest term still to the 3rd degree? $(n^3)$ which would make me think that it is $O(n^3)$, ...
2
votes
0answers
45 views

Estimating the number of permutations with no increasing subsequences of a prescribed length

Let $n\geq 1$ be a positive integer and let $S_n$ be the set of permutations of $\{1, \dots, n\}$ (thought of as non-repeating, exhaustive sequences of elements of $\{1, \dots, n\}$. Let $2 \leq k \...
1
vote
0answers
64 views

What is the limit inferior of $p_n^2/ (\log p_n) \left\lvert 1-e^\gamma\log(p_n+\log^2p_n+\varepsilon_n)\prod_1^n (1-1/p_k)\right\rvert$?

Let $p_n$ be the $n$-th prime number. The $\varepsilon_n:=\varepsilon(p_n)$ in the title is an infinitesimal sequence chosen so that, replacing $p_n$ with $x$, we have$$\lim_{x\to+\infty} \left(\left(...
1
vote
1answer
8 views

Asymptotic relations at infinty

I am attempting to show that If $f(x) - g(x) \ll 1,\, x \to \infty$, then $e^{f(x)}\sim e^{g(x)}, \,x\to \infty$ From the first line, I am able to show that $$ \lim_{x\to \infty} \frac{f(x) - g(...
0
votes
1answer
25 views

Stochastic Convergence Intermediate Textbooks

Currently doing a course in asymptotic theory and wanted to deepen my knowledge about stochastic convergence and related topics. The textbook we are given is "Asymptotic Theory for Econometricians" by ...
0
votes
0answers
24 views

calculate nCr given (n-1)C(r-1) under a modulo fast

Let $_nC_r$ be n choose r or $\frac{n!}{(r!*(n-r)!)}$ Given the value of $_nC_r$ for some n, r, equal to k, how could one find $_{n+1}C_{r+1}$ (mod m) fast computationally (small asymptotic time). ...
0
votes
1answer
78 views

Is $\log(3^n) = O(\log(2^n))$?

How can I prove that this is true/false: $$\log(3^n) \in O(\log(2^n))$$ I know $f(n)$ is $O(g(n))$ if there are positive constants $C$ and $k$ such that: $$f(n) \le C \cdot g(n)$$ whenever $n > k$...
0
votes
0answers
19 views

Asymptotic Expansion for Function with an Embedded Integral [duplicate]

So I'm trying to find the asymptotic expansion as $x \to \infty$ of: $$f(x)=\frac{1}{\bigg[A-\int_{x_0}^x\frac{\lambda^y}{\Gamma(y+1)}dy\bigg]^{\frac{1}{\alpha}}}$$ where $x_0>0$ and $\alpha>0$ ...
28
votes
4answers
4k views

Prove that this function is bounded

This is an exercise from Problems from the Book by Andreescu and Dospinescu. When it was posted on AoPS a year ago I spent several hours trying to solve it, but to no avail, so I am hoping someone ...
0
votes
1answer
55 views

Find the Theta class for the recursion $T(n) = T(3n/4) + T(n/6) + 5n$

$\displaystyle T(n) = T\left(3n\over4\right) + T\left(n\over6\right) + 5n$ is not in the proper form for the Master theorem so I can't really apply it. The only idea I had was changing the $\...
0
votes
2answers
46 views

Can I prove that 2n+1 = O(2n)?

Is 2n+1 = O(2n)? In other words, 2n+1 <= c * 2n for any c and all n > n0? I have plugged in numbers but none that worked. Obviously It is also (n) but I am trying to prove the above. Much ...
1
vote
1answer
31 views

Asymptotic of a convolution integral

$f(x) \ge 0$, $g(x) \ge 0$ are defined on $[0,\infty)$ and $f(x) \sim x^{-a}, \ x \to \infty$, where $a>1$. The integrals $\int_0^\infty f(x)dx<\infty$ and $\int_0^\infty g(x) dx<\infty$. ...
2
votes
4answers
57 views

Intuition: Why will $3^x$ always eventually overtake $2^{x+a}$ no matter how large $a$ is?

I have a few ways to justifiy this to myself. I just think that since $3^x$ "grows faster" than $2^{x+a}$, it will always overtake it eventually. Another way to say this is that the slope of the ...
0
votes
1answer
85 views

limit of sum with binomial coefficients

I have the problem to compute next double sum \begin{equation} \sum_{n=2}^{\infty}\frac{(-1)^n}{n-1}\sum_{k=0}^{n}(3n-k)^j{n\choose k}A^{n-k}B^k\;, \end{equation} being $j\gg1$ an integer number and $...
1
vote
2answers
26 views

How does the number of trees with even order that contain a perfect matching behave asymptotically?

I recently found a nice result for trees of even order that do not contain a perfect matching. This led me to wonder ‘how many’ trees have perfect matchings, asymptotically speaking. Is anything ...
6
votes
2answers
78 views

Bounding a solution of an ODE with a small source

I have an ODE of the form $$ f''(x) + f(x) = \epsilon g(x)$$ with initial conditions $$ f(0) = f'(0) = 0 $$ $g(x)$ is $O(1)$ as $\epsilon \to 0$, and $g(x)$ is as smooth as necessary. Is there a ...
4
votes
1answer
152 views

Functions that preserve asymptotic equivalence

Is there any notion of preserving asymptotic equivalence by a real-valued function? Any facts known about such functions? To clarify what I'm asking I'll introduce one formalization of the idea which ...
2
votes
0answers
56 views

A limit about $\prod_{k=0}^\infty\frac1{1-x^k}$

If $$\sum\limits_{n = 0}^\infty {{a_n}{x^n}} = \prod\limits_{k = 0}^\infty {\frac{1}{{1 - {x^k}}}} ,$$ Prove $${a_n} < \exp \left\{ {\sqrt {\frac{{2\pi }}{3}n} } \right\}$$ and $$\mathop {\lim }\...
0
votes
1answer
34 views

Asymptotics of a real sequence in a Riemann sum

Let $t<0$ and $f(k)\in O(|k|^{t})$ a real function, $k\in\mathbb{Z}$. We consider $$a_n\cdot \sum_{k=1}^n \frac{1}{n} \frac{f(k)}{n^t}$$ where $a_n\subset \mathbb{R}$ and $a_n\xrightarrow{n\...
0
votes
2answers
63 views

How to find the asymptotes of a square root function?

While working out some examples I'm trying to solve, I stumbled on a question that asks to find the asymptotes of the following function: $$y = \sqrt{x^2 + 3}$$ For rational functions I was thought ...
0
votes
0answers
14 views

Rate of growth of the negative part of even cumulants $(\kappa_{k})^{-}$ for mean zero, unit variance $X$

What is the rate of growth of $(\kappa_{2k})^-$ specifically in relation to $(2k)!$? The question was inspired by trying to find a lower bound for $$\kappa(t)+\kappa(-t)$$ by Taylor expanding ...
0
votes
1answer
42 views

Bounding a sum of logarithms

Consider a function $f:(0,\infty)\rightarrow \mathbb{N}$ with argument $\epsilon$. Suppose $f$ is decreasing in $\epsilon$. Let $0<b<1$, $K>0$, $d \in \mathbb{N}$, $\delta>0$. Assume $$ 1\...
22
votes
8answers
4k views

Stirling's formula: proof?

Suppose we want to show that $$ n! \sim \sqrt{2 \pi} n^{n+(1/2)}e^{-n}$$ Instead we could show that $$\lim_{n \to \infty} \frac{n!}{n^{n+(1/2)}e^{-n}} = C$$ where $C$ is a constant. Maybe $C = \sqrt{...
0
votes
1answer
44 views

asymptotic analysis to solve differenial equation

$$ \frac{df(x)}{dx}+\bigg(1+\frac{1}{x}\bigg)f(x)=0 $$ how to solve above differential equation using asymptotic analysis ? Does that give an exact solution ?
1
vote
0answers
76 views

Asymptotic Expansion for a Function involving a Weird Integral

So I'm trying to find the asymptotic expansion as $x \to \infty$ of $$f(x)=\frac{1}{\bigg[A-\int \frac{\lambda^x}{\Gamma(x+1)}dx\bigg]^\frac{1}{\alpha}}$$ Note that $\lambda>0$ and $\alpha>0$. ...
1
vote
1answer
22 views

Use of asymptotically equivalent equations in limits

I was wondering about the steps to show that the following limit does not exists. $$\lim_{x\rightarrow\infty}[\log(x^2-3)-\log(x+2)]$$ I know that by using L'Hopital's Rule and the continuity of ...
0
votes
1answer
65 views

Series Expansion within a fraction

I'm currently reading "The cumulant lattice Boltzmann equation in three dimensions: Theory and validation" from Geier et. al. and have some trouble in a proof. We have given multivariat cumulants (...
0
votes
1answer
15 views

Complexity $\text{O}\left(\log(\log n))^{10}\right)$ vs $\text{O}\left((\log(\log n))^5\right)$?

If the question is not clear, then assume $t=\log(\log n)$, then the question can be re-framed as $\text{O}(t^{10})$ vs $O(t^5)$? So which has a higher order of growth? Thanks.