New answers tagged asymptotics
1
The formal definition of a worst case scenario is that it's an input for which for a given size the algorithm takes the maximum number of steps. There may be more than one such input.
As you discovered, the set of worst case scenarios depends on the algorithm. There's no generic way to find one without knowing the algorithm.
0
The advantage of merge sort in best cases arises when you sort linked lists. For example if you merge one list L1 with another L2 whose elements are all smaller, you will scan L1 and then directly attache L2 at the end of L1. That makes for $O(n_1)$ operations as opposed to $O(n_1+n_2)$.
If you want to work on arrays there are better options than merge sort....
2
The key comparisons only occur in the first while loop. The best case is when L[i] < R[0] or L[0] < R[j], as you exhaust one list after n1 or n2 comparisons. The worst case requires full n1 + n2 comparisons.
The number of moves is constant.
0
If $n=p^a$ then you can compute easily $\varphi(n)$ and $n/\varphi(n)$, and $a$ is a kind of log. If $n$ is arbitrary, use the fact that $\varphi$ is multiplicative. This is not the final answer, but it is a start..
1
From
$P(N,d)
=\frac{N!}{d!N^d},
$,
$\ln(P)
=\ln(N!)-\ln(d!)-d\ln(N)
$.
Since
$\ln(x!)
=x\ln(x)-x+O(\ln(x))
$,
$\ln(P)
=N\ln(N)-N+O(\ln(N))-(d\ln(d)-d+O(\ln(d))-d\ln(N)
$.
Let
$d = \dfrac{c}{\ln(c)}
$
so
$d\ln(d)
= \dfrac{c}{\ln(c)}(\ln(c)-\ln\ln(c))
=c-\dfrac{c\ln\ln(c)}{\ln(c)}
=c+o(c)
$.
Then
$\begin{array}\\
\ln(P)
&=N\ln(N)-N+O(\ln(N))-(d\ln(d)-...
2
You are trying to understand in Example 1 that
$$
\frac{1}{\cos x}=\frac{1}{1-\frac12x^2+o(x^3)}=1+\frac12 x^2+o(x^2)
\quad\textrm{as }x\to 0.
$$
Apostol says that this is "from part (e) of Theorem 7.8", i.e.,
As $x\to a$, if $g(x)\to 0$, then
$$
\frac{1}{1+g(x)}={1-g(x)+o(g(x))}.
$$
So if you let $g(x)=-\frac12x^2+o(x^3)$, then
$$
\sec x
= 1-(-\...
1
First off, you know that:
$\begin{align*}
2^{2 n}
&= (1 + 1)^{2 n} \\
&= \sum_{0 \le k \le 2 n} \binom{2 n}{k} \\
&\ge \binom{2 n}{n}
\end{align*}$
so that $\binom{2 n}{n} = O(2^{2 n})$.
More precise estimates are from Stirling's approximation, in the variant given by Robbins ("A Remark on Stirling's Formula", AMM 62:1 (1955), 26-...
2
The OEIS sequence A000984 "Central binomial coefficients" contains the line
Using Stirling's formula in $A000142$ it is easy to get the asymptotic expression $a(n) \sim 4^n / \sqrt{\pi n}.$
which implies that $a(n) := \binom{2n}{n} = O(4^n).$
The Wikipedia article Central binomial coefficient has this expression also using Stirling's approximation ...
3
$f(n)$ is $O(n^4)$ and $\Omega(n^4)$, i.e. $f(n) = \Theta(n^4)$.
Assuming that the logarithm is base $2$, $g(n) = 16^{\log(n)} = (2^4)^{\log(n)} = (2^{\log(n)})^4 = n^4$.
0
$$\sum_{i=1}^n i=\frac{n(n+1)}2.$$
By the definition of $f(n)\in O(n)$ it should be true that
$$\lim_{n\to\infty}\frac{\sum_{i=1}^n i}n= \text{some constant}.$$
But
$$\lim_{n\to\infty}\frac{\frac{n(n+1)}2}n=\lim_{n\to\infty}\frac12(n+1)=\infty$$
and not a constant.
That is,
$$\sum_{i=1}^n i\not\in O(n).$$
EDIT
I am sorry for mistaking "big $\Omega$" ...
3
It suffices to prove that $F_n=o(2^n)$. One way to do this is to take the
generating function $\sum_n F_nx^n=1/(1-x-x^2)$ and observe it converges
absolutely at $x=1/2$.
For a very low-brow approach,
pick a number $a$ with $\frac12(1+\sqrt5)<a<2$, say $a=5/3$. We claim that
$F_n\le a^n$. This is OK for $n=0$, $1$. Inductively,
$$F_n\le a^{n-1}+a^{n-2}=...
5
Let's denote your sum by $S(m,p)$. First of all, we have
$$S(m,p)=\sum_{k=1}^{\infty}\big(1-(1-p^k)^m\big)=\color{blue}{\sum_{j=1}^{m}(-1)^{j-1}\binom{m}{j}\frac{p^j}{1-p^j}}.$$
(The first equality is obtained, with $a_k=1-(1-p^k)^m$, from
$$\sum_{k=1}^{n}k(a_k-a_{k+1})=\sum_{k=1}^{n}ka_k-\sum_{k=1}^{n+1}(k-1)a_k=\sum_{k=1}^{n}a_k-na_{n+1};$$
to get the ...
5
I am aware of this answer as well as of
this question in MO
and its answer. There are, of course, some overlaps, but I proceed
differently and answer the questions of the OP.
To fix notation, we consider $a$ close to 1, $b=b(a)=\log(a)$ and $L=L(a)$ the solution
close to 1 of $L=a^{L}(=\exp(b\,L))$.
Keep in mind that
$L$ is close to 1 and $b$ is close to ...
5
It's clear that the Fibonacci numbers are increasing, so
$$
F(n+2) > 2F(n).
$$
That's good enough to guarantee exponential growth.
2
In my opinion, you missed an important term in the asymptotics of $H_n$
$$H_n=\gamma +\log \left({n}\right)+\frac{1}{2
n}+O\left(\frac{1}{n^2}\right)$$ which would make
$$H_{mn}-H_m-H_n\sim-\gamma -\frac{1}{2 m}-\frac{1}{2 n}+\frac{1}{2 mn}+\cdots$$
1
Assume I would like to look for the solutions to the recurrence $T_n$ of the form $T_n = x^n$ for some $x \ne 0$. Plugging that into the recurrence, you get
$$
x^n = x^{n-3} + 2x^{n-4} + 4x^{n-6}
$$
and now cancel $x^{n-6}$ from both sides, yielding your polynomial.
Indeed, the resulting polynomial $x^6-x^3-2x^2-4$ has one positive root $r \approx 1.51432$ (...
0
This answer derives Stirling's Asymptotic Approximation by writing the log of a factorial as a Riemann-Stieltjes Integral.
Theorem $\bf{1}$: (Asymptotic Approximation of the Central Binomial Coefficients)
$$
\lim_{n\to\infty}\frac{\sqrt{\pi n}}{4^n}\binom{2n}{n}=1\tag1
$$
Note that Theorem $1$ is equivalent to Wallis' Product for $\pi$.
Proof:
The ...
0
So you are looking for
$$
\mathop {\lim }\limits_{y\; \to \;\infty } {{\Gamma \left( {s,iy} \right)} \over {\Gamma \left( s \right)}}
= \mathop {\lim }\limits_{y\; \to \;\infty } Q\left( {s,iy} \right)\quad \left| {\;y \in R} \right.
$$
(and we do not specify, for the moment, the field for $s$).
It is known that the Regularized Incomplete Gamma has the ...
2
Let $J(z) = \Gamma(a) I(1)$. If $b < 1$, the integral $J(0)$ converges and
$$\lim_{z \to 0^+} J(z) = J(0) =
\frac {{_2 F_1}(1 - b, 1 + a - b; 2 - b; -1)} {1 - b}.$$
If $b \geq 1$, subtract $t^{b - 2} e^{-z t}$ from the integrand and prove that the resulting integral is asymptotically smaller than $J(z)$. Then
$$J(z) \sim \int_1^\infty t^{b - 2} e^{-z t} ...
3
Easy general method needing no cleverness, useful for many problems, See the diagram below:
For a function such as (natural) logarithm with $f(x) > 0$ and $f'(x) > 0,$ we get
$$ \int_{a-1}^b \; f(x) dx < \sum_{k=a}^b \; f(k) < \int_{a}^{b+1} \; f(x) dx $$
Here $f$ is log base e, take $a=2$ and $b=n,$ later we will take $n=300$
$$ \int_{1}^n ...
19
Let $n\in\Bbb N$. We have $e<3$ and hence
$$3^{3n}>e^{3n}=\sum_{k=0}^\infty\frac{(3n)^k}{k!}.$$
As all summands are positive, this implies
$$ 3^{3n}>\frac{(3n)^k}{k!}=\frac{3^kn^k}{k!}$$
for all $k$. In particular, for $k=3n$, this becomes $3^{3n}>\frac{3^{3n}n^{3n}}{(3n)!}$, or
$$(3n)!>n^{3n}.$$
For $n=100$, this gives us
$$300! > 100^{...
1
don't need Stirling. For a function such as logarithm with $f(x) > 0$ and $f'(x) > 0,$ we get
$$ \int_{a-1}^b \; f(x) dx < \sum_{k=a}^b \; f(k) < \int_{a}^{b+1} \; f(x) dx $$
Here $f$ is log base e, take $a=2$ and $b=n$
$$ \int_{1}^n \; \log x \; dx < \sum_{k=2}^n \; \log k < \int_{2}^{n+1} \; \log x \; dx $$
An antiderivative of $\...
1
Given function $$ f(x) = x \ln \bigg (e + \cfrac{1}{x} \bigg)$$
It should be obvious that there must be something bad with the function, when arguments inside the $ \ln ( \cdot) $ goes to zero, and that is the case when $x \to \cfrac{1}{e}$, resulting value of $\ln(\alpha) \to - \infty$ as $y \to 0$ , where $ \alpha = e + \cfrac{1}{x}$, which would make $f(...
0
Observe that
$$\lim_{x\to -1/e^{-}}\ln\left(e+\frac1x\right)=-\infty$$
Then,
$$\lim_{x\to -1/e^{-}}x\ln\left(e+\frac1x\right)=\left[\lim_{x\to -1/e^{-}} x\right]\left[\lim_{x\to -1/e^{-}}\ln\left(e+\frac1x\right)\right]=+\infty$$
So, $x=-1/e$ is an horizontal asymptote.
1
Integrate $\frac{y'}{y^2}\geq 2$ from time $t=t_0$ to $t=t_1$, $t_0<t_1$ gives
$$
\int_{t_0}^{t_1}\frac{y'}{y^2}\,\mathrm{d}t \geq \int_{t_0}^{t_1}2\,\mathrm{d}t
$$
and
$$
LHS=\int_{y(t_0)}^{y(t_1)}\frac{\mathrm{d}y}{y^2}=\frac1{y(t_0)}-\frac1{y(t_1)}.
$$
5
This is just an attempt to come nearer to the problem, perhaps the last step can be seen as a proof for the right equality in your last equation. Maybe this relatively easy-to-see point of view has escaped your attention and you might do something more with this ansatz. (For the cursory reader the link to an answer of mine in MO(jun 2017) might be ...
2
If $f\in o(x)$ and $g\in O(f(x))$, then $\lim_{x\to \infty}\frac{f(x)}x=0$ and $|g(x)|\le M f(x)$ for some $M$ and all $x\gg 0$. It follows that $\lim_{x\to \infty}\frac{g(x)}x=0$, i.e., $g\in o(x)$.
(But $f\in o(x)$ and $g\in o(x)$ does not imply $g\in O(f(x))$)
2
U. Zannier in his paper `On the Distribution of Self-Numbers' proves a theorem about the number of self numbers less than $x$, specifically that $A(x)= Lx + O(\log^2(x))$ for some positive $L$. You can invert this function to get a statement about the $n$th self number growing linearly (in the same way that one can invert the prime number theorem $\pi(x) \...
3
By the most recent bound on Linnik's Theorem, there is an absolute constant $c$ such that for every prime $q < cp_n^{1/5}$, there is a prime $p < p_n$ such that $p \equiv 1 \pmod{q}$. Your least common multiple is therefore divisible by all primes below $cp_n^{1/5}$. The prime number theorem implies that the product of all primes below $cp_n^{1/5}$ is $...
0
When $p$ is small, the leading-order probability that a cell $(\pm x,\pm y)$ is infected is $${x+y\choose x}{t\choose x+y}p^{x+y}\\ \approx {(tp)^{x+y}\over x!y!}$$
If I count the points where this approximation is greater than $1$, that implies that, for small $p$, the region is bounded by the curve $$tp=\sqrt[|x|+|y|]{|x|!|y|!}$$
Unfortunately, the ...
6
(This is more like a comment with images)
Here are some simulations of the values $c = c(p)$ using the grid of size $1000\times1000$ and $500$ steps together with some fitting curves.
$\hspace{8em}$
The data clearly deviates from the polynomial $2p^2$, and although the above plot may seem to suggest that $c(p)$ assumes a nice closed form, I believe that ...
3
Seems fine but it is easier to note that
$$
n+1\leq 2n
$$
for $n\geq 1$ whence
$$
(n+1)^3\leq (2n)^3=8n^3
$$
for $n\geq 1$ as desired.
0
Some extremely rough estimates / possible approach / too long for a comment
It seems $c$ goes as $p^2$.
Following OP, let $X_t$ be the no. of infected cells at time $t$. This is a sort of "area". $X_1 = 1$.
Let $B_t$ be the no of non-infected cells which are next to some infected cells. This is a sort of "boundary" or "circumference" of the "area" $X_t$....
2
Your differential equation has closed-form solutions
$$ \eqalign{f \left( t \right) &=c_{{1}}{t}^{1/2-a/2}{{ J}_{-\sqrt {{a}^{2}-2\,a
+4\,b+1}}\left(2\,{\frac {\sqrt {b\epsilon}}{\sqrt {t}}}\right)}\cr &+c_{{2
}}{t}^{1/2-a/2}{{ Y}_{-\sqrt {{a}^{2}-2\,a+4\,b+1}}\left(2\,{\frac
{\sqrt {b\epsilon}}{\sqrt {t}}}\right)}}
$$
where $J$ and $Y$ are Bessel ...
1
Here is a key lemma (which you can and should prove for yourself) that helps to resolve so many questions of this type. I'll phrase it in terms of functions of $x$ where $x\to\infty$, although it holds for other domains as well.
Lemma: Let $f,g\colon [1,\infty)\to[2,\infty)$ be functions. If $\log f(x) = o(\log g(x))$ as $x\to\infty$, then $f(x) = o(g(x))$ ...
1
Yes it does. Let $t_N$ denote the algorithm time. Let $f_N = \max\{t_M/M^2:M\le N\}$. Suppose $f_N$ diverges. Then $t_N$ fails to be $O(\sqrt{f_N} N^2)$. Therefore $f_N$ does not diverge. Since $f_N$ is a non-decreasing sequence, it must be bounded. Set $C= \sup f_N$. Then $t_N \le C N^2$.
1
$\log((1/n) + n^2 )$
If we just focus on the term inside of the logarithm.
$ let x = 1/n + n^2$
As n grows, we notice that the 1/n term effectively becomes zero and the overpowering term is $n^2$
We can now state that $\log((1/n) + n^2 )$ has growth $log(n^2)$ when n gets large.
We know from logarithms that $log(a^b) = b* log(a)$
So $log(n^2)$ can be ...
-1
$n^2+\frac{1}{n}$ is $O(n^2)$.
$\log(n^2)=2\log n$ is $O(\log n)$
1
My interpretation:
First of all, $f$ should really be $f^J$ since the domain of $f$ is $\mathbb{R}^J$ so different $J$'s $\implies$ different $f$'s.
Then the thing you want to prove becomes (edit in red):
$$\frac{1}{J} \sum_{j=1}^J f^\color{red}{J}_j(X) \xi_j\rightarrow_p0 \text{ as $J\rightarrow \infty$}$$
Then comparing to your theorem for triangular ...
0
It is not true that $f(n)=\Theta((n/2)!)$.
$$\begin{aligned}
f(n)&=\min_{k\in\mathbb N_+, n-k> 0,\ n!-k!(n-k)!> 0}\{\max\{k!,\,(n-k)!,\,(n!-k!(n-k)!)\}\\
&=\min_{0\lt k\lt n}\{\max\{k!,\,(n-k)!,\,(n!-k!(n-k)!)\}\\
&=\min_{0\lt k\lt n}\{n!-k!(n-k)!\}\\
&=n!-\max_{0\lt k\lt n}\{k!(n-k)!\}\\
&=n!-1!(n-1)!\\
&=(n-1)(n-1)!\\
&=\...
2
Following a more elementary route we will first break the integral in two pieces:
$$B(\frac{N+1}{N+2};N+1,p+1)=B(N+1,p+1)-I\\I=\int^{1}_{\frac{N+1}{N+2}}x^{N}(1-x)^pdx$$
Perform the change of variables $t=1-\frac{x}{N+2}$:
$$I=\frac{1}{(N+2)^{p+1}}\int_{0}^1t^p(1-\frac{t}{N+2})^{N}dt$$ However it is possible to estimate that
$$(1-\frac{t}{N+2})^{N}=e^{-t}(...
2
Method 1
Set $F(x)=\int_0^x f(t)\,\mathrm d t$. Then $$F(x)=F(0)+F'(0)x+\frac{F''(0)}{2}x^2+o(x^2)$$
$$=f(0)x+\frac{f'(0)}{2}x^2+o(x^2)=ax+\frac{b}{2}x^2+o(x^2).$$
Method 2 (Using your idea)
Since $\varepsilon (x)\to 0$ when $x\to 0$, there is $M>0$ and $\delta >0$ s.t. $|\varepsilon (x)|\leq M$. Therefore, if $|x|<\delta $, $$\left|\int_0^x t\...
2
As Paul Enta already answered, the integral can be exactly computed.
$$J=\int_z^\infty \exp\left({- \frac { \pi^2}{16}(y-x)^2}\right) \,d y=\frac{2 }{\sqrt{\pi }}\left(1+\text{erf}\left(\frac{\pi}{4} (x-z)\right)\right)$$
$$I=\int \frac{\cos \left(\frac{\pi x}{2 z}\right)}{z}J \,dx=\frac{2 e^{-\frac{1}{z^2}}}{\pi ^{3/2}}\left(\text{erf}\left(\frac{\pi z (...
4
Changing $x=zt, y=zt+u$, on can express
\begin{align}
I&=\int_{-z}^z \frac{\sin \left(\frac \pi {2z} x + \frac \pi 2 \right)} z \int_z^\infty \exp\left({- \frac {(y-x)^2 \pi^2}{16}}\right) \,d y d x\\
&=\int_{-1}^1\cos\frac{\pi t}{2}\,dt\int_{z(1-t)}^\infty \exp\left( -\frac{\pi^2}{16} u^2 \right)\,du
\end{align}
It can be integrated by parts,
\...
6
Write $a_n = 1 - \epsilon_n$ and notice that $(\epsilon_n)$ solves
$$ \epsilon_{n+1} = \epsilon_n - \frac{\epsilon_n^2}{2}.$$
For the purpose of future use, we allow $\epsilon_0$ to take any value in $(0, 1]$. This type of sequence is well-studied, and here is a method of extracting asymptotic forms up to certain order in a bootstrapping manner.
Since $0 \...
2
$$\sum_{n\le x}(\psi(\frac xn)-\vartheta(\frac xn))\Lambda (n)=O(\sum_{n \le x}(\frac xn)^{1/2} (\psi(n+1)-\psi(n)))\\ = O(\psi(x)+\sum_{n \le x}((\frac xn)^{1/2}-(\frac x{n+1})^{1/2}) \psi(n)) $$
$$ = O(x+\sum_{n \le x}((\frac xn)^{1/2}-(\frac x{n+1})^{1/2}) n)= O(x+\sum_{n \le x} (\frac xn)^{1/2}) = O(x)$$
where I used $\psi(x)-\psi(x/2) = O(\log {x\...
1
First we want the "$O()$" part of the answer.
We want $A, x_0$ s.t. $Ax^3 > 2x^3+3x^2+1$ for $x>x_0$.
Divide through by $x^3$ to get
$\displaystyle A > 2+\frac{3}{x} + \frac{1}{x^3}$
Now let $x=x_0 =1 $. Then $A > 6$. But are we sure $A=6 x_0=1$ is a suitable example?
Now, if $x>x_0$, then
$\displaystyle \frac{3}{x} < \frac{3}{x_0}$ ...
0
$a_n$ behaves like $1+\frac2n$. Convergence is very slow...
Proof: Let $b_n=a_n-1$. Then the recursion is $b_{n+1}=\ln(1+b_n).$ Therefore
the sequence $b_n$ is strictly decreasing with limit $0$. Consider
now that $\ln(1+x)=x-\frac12x^2+o(x^2)$ as $x\to0.$ This gives
$$\frac1{b_{n+1}}=\frac1{\ln(1+b_n)}=\frac1{b_n(1-\frac12b_n+o(b_n))}=\frac1{b_n}+\frac12+o(...
1
Assume $\beta = 1/x > 0$. Let $p = 2 + n u$, then
$$\frac {(p - 1) (2 n - p)!} {n! (n + 1 - p)!} \beta^{-p} \sim
f(u) e^{n \phi(u)},
\quad n \to \infty, \\
f(u) = \frac u {\beta^2} \sqrt {\frac {1 - u} {2 \pi n (2 - u)^3}}, \\
\phi(u) = -u \ln \beta - (1 - u) \ln(1 - u) + (2 - u) \ln(2 - u).$$
The maximum of $\phi(u)$ is located at $u_0 = (2 \beta - 1)/(\...
0
When asked to find the asymptotic behavior, you can discard terms that are negligible in front of the dominant term. Here you have two exponentials, in base $4$ and $3^2$, and by Stirling we know that the third term is asymptotic to $n^3\log n$. Hence $3^{2n-1}$ is dominant (exponentials grow faster that polynomials) and
$$f(n)\in O(3^{2n-1}).$$
We can ...
Top 50 recent answers are included
