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


12

$O(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

$O(\log(n))$ and $O(\log(n-1))$ contain the same set of functions. The inclusion $O(\log(n-1)) \subseteq O(\log(n))$ is trivial. As for $O(\log(n-1)) \supseteq O(\log(n))$, let $f(n) \in O(\log(n))$ and let $c \ge 1$ and $n_0 \ge 3$ be such that: $$ f(n) \le c \log(n) \quad \forall n \ge n_0. $$ We have: $$ f(n) \le c \log(n) = c + c \log(n/2) \le c + c \...


2

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


2

The answers and comments by other users here do a good job of explaining how the notation works, so I figure I'll explain why the notation is used this way. The reason for the notation is already evident in your question: writing out the set inclusion explicitly makes it way more verbose. When you are learning asymptotic notation for the first time, it is ...


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.


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


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