9

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 ...


7

Part 2 $$ \newcommand{\TR}{\mathbb{R}} \newcommand{\TN}{\mathbb{N}} \newcommand{\subsets}[1]{\mathcal{P}(#1)} \newcommand{\setb}[1]{\left\{#1\right\}} \newcommand{\land}{\text{ and }} $$ Algorithms Are there cases where existing intuition on O-notation may not hold? You may find that your existing intuition does not hold when the input-set is something else ...


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! $$


2

I guess the proof is fine except for the fact that you have used same costant in two different eqns. Even if you use(and you must use, because the constant you choose is arbitrary) two different conts say c1 and c2, the solution will imply the same.


2

You just need to show that $$ \lim_{n \to \infty} \frac{\log^r n}{n^p} = 0. $$ This is trivial if $r \le 0$ since $\frac{\log^r n}{n^p} = \frac{1}{n^p \log^{-r} n}$ and $\lim_{n \to \infty} n^p \log^{-r} n = +\infty$. For $r>0$, you can use l'Hôpital's rule $\lceil r \rceil$ times to obtain: $$ \lim_{n \to \infty} \frac{\log^r n}{n^p} = \lim_{n \to \...


1

Let's consider only $r>0$. For $\ln(n)^r \in o(n^p),p>0$ is enough to show $\ln(n) \in o(n^\alpha)$, for $\frac{p}{r}=\alpha>0$, because $\frac{\ln(n)^r}{n^p} =\left(\frac{\ln(n)}{\sqrt[r]{n^p}}\right)^r$ and $r$ power is continuous function. So we come to limit $$\lim\limits_{n \to \infty}\frac{\ln(n)}{n^\alpha}=\lim\limits_{n \to \infty}\frac{\...


1

An example is $f(n) = 2 ^ {2^n}$. Now, $f(n-1) = 2 ^ {2^{n-1}}$ and we have $\frac{f(n-1)}{f(n)} = \frac{1}{2^{2^n - 2^{n-1}}} = \frac{1}{2^{2^{n-1}}}$. Hence, $f(n-1) \not \in \Theta(f(n))$. In this example, $k = 1$.


1

The notations $f = \Omega(g)$ and $f \geq \Omega(g)$ are identical. In both cases, they mean that there exists a positive constant $C$ such that for large $n$, $f(n) \geq Cg(n)$. You can estimate the sum as follows: $$ \sum_{i=0}^n \sqrt{i} \log_2^2 i \geq \sum_{i=n/2}^n \sqrt{i} \log_2^2 i \geq \sum_{i=n/2}^n \sqrt{n/2} \log_2^2 (n/2) \geq \frac{n}{2} \cdot ...


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 ...


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