# Tag Info

16

In order to compare 2 complexities just calculate a limit of their ratios as below: \displaystyle\begin{align*} \lim_{n\to\infty}\frac{n^2log(n)}{n^2\sqrt{n}} &= \lim_{n\to\infty}\frac{log(n)}{\sqrt{n}} = \lim_{n\to\infty}\frac{log(\sqrt{n})^2}{\sqrt{n}} = \lim_{n\to\infty}\frac{2log(\sqrt{n})}{\sqrt{n}} \\ &\underset{\left| k = \... 12O(n^2 \times \log(n))$is greater than$O(n^2)$but it is smaller than$O(n^{2 + \epsilon})$for any$\epsilon > 0$, however small$\epsilon$is (see here). In particular, it is smaller than$O(n^{2.5})$. You're basically comparing the growth of$\log$and square root. 5 Your expression is $$E = \frac{cn^2}{\log \frac{n(n+1)}{2}}$$ where$c$is some constant. The simple upper bound for$E$is $$E\le c n^2$$ which implies that$\mathcal{O}(n^2)$. For a better bound $$E = \frac{cn^2}{\log \frac{n(n+1)}{2}} = \frac{cn^2}{ 2 \log n + \log n - \log 2 }$$ Now it is an easy verification that$E$is$\mathcal{O}(\frac{n^...

5

As $n^{0.5}$ is always greater than $\log(n)$, $O(n^{2.5})= O(n^2 \times n^{0.5})$ is always bigger than $O(n^2 \times \log(n))$. Anyway, you should consider your real algorithm usage scenario to choose one which fits the best.

4

There is an explicit formula for $\sum_{i=0}^n i^3$, but even without it, you can estimate $$\int_0^n x^3 \, dx \leq \sum_{i=0}^n i^3 \leq \int_1^{n+1} x^3 \, dx.$$ Since $\int x^3 \, dx = x^4/4$, this shows that the sum is very close to $n^4/4$, and in particular is $\Theta(n^4)$. (The explicit formula states that the sum equals $n^2(n+1)^2/4$.)

4

Counterexample: $f(n)=n!$ As $f(n)$ is $n$ times bigger than $f(n-1)$, it is clear that $f(n-1) \neq \Theta(f(n))$.

3

Pick $n_0 = \max\{ -\log c, 10 \}$. Then, for all $n \ge n_0 \ge 10$: $$2^n = \frac{4^n}{2^n} \le \frac{4^n}{2^{n_0}} \le \frac{4^n}{1/c} = c \cdot (4^{n-10} \cdot 4^{10}) < c \cdot (4^{n-10} \cdot 10!) \le cn!$$

3

Part 1 I'm going to do something I decided I wouldn't do: try to nutshell my research on this topic. I'll go over on how the algorithmic O-notation must be defined, why it is probably not what you've been taught, and what other misconceptions float around this topic. I wrote this in the form of an imaginary discussion. The following discussion is based on ...

3


1

What I recommend first is to notice that if you're looking at the complexity of the function $3x^2+2x+1$, really all you should care about is the function $x^2$. because if you will prove that $x^2 = \omega(xlogx)$ then adding the $2x + 1$ won't ruin that proof since $x^2$ is polynomially bigger than $2x + 1$ and so we can just look at the $x^2$. (I will ...

1

The easiest way is to check that $\lim_{x \to \infty} \frac{3x^3 + 2x +1}{ x \log x} = +\infty$, which is a sufficient condition for $3x^3 + 2x +1 \in \omega(x \log x)$. $$\lim_{x \to \infty} \frac{3x^3 + 2x +1}{ x \log x} = \lim_{x \to \infty} \frac{3x^3}{ x \log x} = \lim_{x \to \infty} \frac{3x^2}{ \log x} = \lim_{x \to \infty} 6x^2 = +\infty.$$

1

$2^n$ is the product of n numbers which are all equal to 2. n! is the product of n numbers from 1 to n. Once n ≥ 3, if you increase n by 1, $2^n$ is doubled, while n! is multiplied by 4 or more. So basic maths shows that for n ≥ 3, $n! ≥ 6/64 \cdot 4^n$. Given any C > 0 from the definition, you calculate how large n would have to be to make $2^n < 6/... 1 One way to prove$f(n) = o(g(n))$is to prove that:$\begin{align*} \lim_{n \to \infty} \frac{f(n)}{g(n)} &= 0 \end{align*}$In this case, you know that:$\begin{align*} \lim_{n \to \infty} \frac{2^n}{n!} &= 0 \end{align*}$since the series for$e^x$converges for all$x$, so it converges for$x = 2$, and the terms of a convergent ... 1 The clearest, most complete, introduction to asymptotics I've yet found is Hildebrand's "Short Course on Asymptotics". Somewhat heavy going, but nailing the concepts down is crucial. BTW,$2 n^2 + 3 n + 1 = 2 n + \Theta(n)$is clearly wrong, it presumably was meant to be$2 n^2 + 3 n + 1 = 2 n^2 + \Theta(n)$1 We need to inspect the factors after that, since the factors of$n!$grows linearly while the factors of$2^n$stays constant. We use the first four factors and the rest of them to formulate the constant factors used for the big-O proof. It is obvious that$2^4 = 16$while$4! = 24$. However, by observing the factors, we notice$2^n$has$16\$ as a factor and ...

Only top voted, non community-wiki answers of a minimum length are eligible