4
You can do a Taylor development (at $\infty$) and see how that goes. Namely, write
$$
\frac{1}{n^{2/3}+(-1)^n}
= \frac{1}{n^{2/3}} - \frac{(-1)^n}{n^{4/3}} + o\!\left(\frac{1}{n^{4/3}}\right) \tag{1}
$$
using that $\frac{1}{1+x} = 1-x + o(x)$ when $x\to 0$. This means that
$$
\frac{\cos n}{n^{2/3}+(-1)^n}
= \underbrace{\frac{\cos n}{n^{2/3}}}_{a_n} - \...
4
I suppose that you can also evaluate $K \in [1,2]$.
Consider the power of exponent near the maximum: $$e^{f(k)}=e^{f(k_{max})+\frac{1}{2}f''(k_{max})(k-k_{max})^2+...}$$
It is supposed that other terms of the series in the power of the exponent can be omitted (do not contribute into the main asymptotics term). In many cases such approximation works well.
$$f(...
3
There is indeed a mistake in this example. $$\lim_{n\to\infty}\frac{10n^2-5n+6046}{n^2}=10\ne \infty$$
So $10n^2-5n+6046\ne \omega(n^2)$. However we can say that $10n^2-5n+6046=\Omega(n^2)$.
2
Contour integral over three line segments
It can be shown that
$$
\frac1\pi\arg\zeta\left(\frac12+iT\right)={1\over2\pi i}\int_\mathcal L{\zeta'\over\zeta}(s)\mathrm ds
$$
in which $\mathcal L$ represents line segments $1/2-iT\to2-iT\to2+iT\to1/2+iT$. Since $|\log\zeta(2+it)|\le\log\zeta(2)$ for all $t\in\mathbb R$, we see that the integral on the line ...
2
The if and only if is true.
If $f(n) \in O(g(n))$ then there is some $N$ and $k>0$ such that for $n \geq N$,
$$f(n) \leq k g(n).$$
This means that for $n \geq N$, $g(n) \geq \frac{1}{k} f(n)$,i.e. , $g(n) \in \Omega(f(n))$.
The other way around is very similar.
2
The eigenvalues of an $N$ by $N$ matrix (and thus the spectral radius) can be computed in $O(N^{3})$ time by Francis's algorithm (aka the implicitly shifted QR method.)
The Arnoldi method for computing the largest magnitude eigenvalue might be faster than computing all of the eigenvalues, particularly if the matrix is sparse. If the matrix is dense, then ...
2
This is false in general, take $a_n=\frac{(-1)^n}{\log n}$ and $b_n=\frac{1}{n}$, then $\frac{b_n}{a_n}=(-1)^n\frac{\log n}{n}\rightarrow 0$, $\sum a_n$ converges but $\sum b_n$ diverges.
2
$$\ln \left(1+xz\right)^{1/z} = \frac1z \ln(1+xz) = \frac1z \left(xz - \frac12 (xz)^2 + O(z^3)\right) = x - \frac12 x^2z +O(z^2)$$
So:
$$(1+xz)^{1/z} = e^x e^{-\frac12x^2z+O(z^2)} = e^x \left( 1 - \frac12 x^2z + O(z^2) \right) = e^x - \frac12 e^x (zx^2) + O(z^2)$$
1
I think this is true. As Greg Martin says, it's only reliable to prove it from the definitions. Throughout the proof I'll only write one $\delta >0$, because we can take the minimum of all $\delta_i$'s and call it $\delta$. \
Let $M>1$ there exists $\delta >0$ such that $|\frac{f(x)}{g(x)}|>\sqrt{M}$ and $|g(x)|>\sqrt{M}$ whenever $0<|x-a|&...
1
$A$ is in $\Theta (n \log n)$ and $B$ is in $\Theta (2^n)$ - $B$ can not be more efficient than $A$?
Let me rephrase your question slightly in the way I understand it:
Given two functions $f(n) \in \Theta(n\log n)$ and $g(n) \in \Theta(2^n)$, is it always true that $f(n)\in o(g(n))$?
Then the answer is yes, as $n\log n \in o(2^n)$. More precisely, you know by definition that there are positive constants $c$ and $k$ such that for large enough $n$, $f(n)\leq ...
1
You can compute the spectral radius using Gelfand's formula. Otherwise, obviously computing the spectral radius is at least as hard as finding the largest (or smallest) root of a polynomial, which has been studied, and engendered great confusion.
1
I think I would compare their log's. $\ln f(n)$ is linear. $\ln g(x) = \sqrt{n} \ln n << \sqrt{n}\sqrt{n} = n$. So $f$ is bigger than $g$ by a good bit.
1
It seems that you have struggles with understanding what Big-O means in the first place, so I've decided to add some further details, although the comments and the already given answer are sufficient.
The Big-O notation was first introduced by Paul Bachmann in "Analytische Zahlentheorie (1894)" for a way of expressing approximation. On page $401$ ...
1
You have:
$\begin{align*}
n^3 / 3 + 6 n^2 - 10000
&= O(n^3) \\
5 n \log 2 n + 6 n
&= O(n \log n)
\end{align*}$
You prove the above and take it from here.
1
You are right with your idea that the order of the elements in $val$ effects the total running time costs of your program. However, it has no effect on its asymptotic running time complexity in terms of Big-O analysis.
For the sake of simplicity let us introduce something what we will call time unit.
Accessing an element in an array via index $i$ takes one ...
1
I think the previous answer that is currently ticked is wrong please read this link
c's value must be a constant and independent of n, but may depend on n0 which in the link is referred to as k.
So, it can be 1.
(If this is wrong please delete this)
To prove f(n)=ω(g(n)) we must prove that
$\lim_{x \to \infty}\frac{ f(n)}{g(n)}$=$\infty$
which is proved by ...
Only top voted, non community-wiki answers of a minimum length are eligible
