A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.
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.


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


3

$\mathcal{O}\Big(\log{n} + \log{(n-1)} + \ldots + \log{(1))}\Big) = \mathcal{O}(\log{n})$ That is not right. When $n$ is large enough, $$\begin{align} \log{n} + \log{(n-1)} + \ldots + \log(1) &\ge \log{n} + \log{(n-1)} + \ldots + \log(n/2)\\ &\ge n/2 \log(n/2)\\ &=\Theta(n\log n) \end{align}$$ More precisely, since $n!\sim {\sqrt{2\pi n}\left(\...


2

No. You can't. As $\lim_{n\to\infty} \frac{n!}{n! \times n} = 0 $. Hence, $n! \times n = \omega(n!)$ or $n! = o(n\times n!)$ (little-oh).


2

Define $M = \max(|a_0|/a_m, |a_1|/a_m, \ldots, |a_{m-1}|/a_m)$, and take $c = a_m/2$ and $n_0 = 2mM$. Then for $n \geq n_0$, $$ \begin{align*} f(n) &= a_m n^m \left(1 + \frac{a_{m-1}}{a_m} \cdot \frac{1}{n} + \cdots + \frac{a_1}{a_m} \cdot \frac{1}{n^{m-1}} + \frac{a_0}{a_m} \cdot \frac{1}{n^m}\right) \\ &\geq a_m n^m \left(1 - \frac{M}{n_0} - \cdots ...


2

The last step is incorrect. $\mathcal{O}\Big(\log{n} + \log{(n-1)} + \ldots + \log{(1))}\Big)$ is not $\mathcal{O}(\log{n})$. You made the same mistake as What goes wrong with sums of Landau terms?. See also What is the asymptotic runtime of this nested loop?.


2

I am afraid that you could have been more careful. I know that by L'Hospital's rule we can reduce it to $\lim_{n \to \infty} \frac{n+1}{n}$ which is a constant and hence $n = \theta (n+1)!$. By L'Hospital's rule we have $$\lim_{n \to \infty} \frac{(n+1)!}{n!}=\lim_{n \to \infty} (n+1)=\infty\,, $$ which means $(n+1)! = \omega(n!)$, or what is equivalent, ...


2

This kind of thing just doesn't work. For example, one of your intermediate terms is $O(1)/O(\log n)$. However any function $f$ can be written as $g/h$ where $g=O(1)$ and $h=O(\log n)$. If $f=O(1)$, then let $g=f$ and $h=1$. If $f=\Omega(1)$, then let $g=1$ and $h=1/f$. For a more formal treatment, try to rewrite each of your statements that involve ...


2

Since it seems to be an unfulfilled clause in this discussion, let me add a quick proof that the following equations hold: $ log(n) \leq \sqrt {n} $ for all $n \geq n_0$, where $n_0$ is some constant. proof by L'Hospitals rule: $$\lim_{n\to \infty } \frac{\log(n)}{\sqrt{n}} = \frac{\frac{1}{n}}{\frac{1}{2\sqrt{n}}} = \frac{2\sqrt{n}}{n}=\frac{2}{\sqrt{n}} ...


2

When it comes to instances like this, I prefer to think about conceptually "promoting" and "demoting" lower order terms. For instance, if we wanted to upper bound: $$f(n) = 32 + 11 \log_2 n + 5 n + 2 n^2$$ We know (by intuition or limits) that $n^2$ is the fastest growing term here. Thus, we should be able to bound $f(n)$ by $n^2$. By this, I mean we can ...


1

First let us notice that $\log s = n^{o(1)} = o(n)$, and so $\mathit{poly}(\log s, n) = \mathit{poly}(n)$. This shows that the first summand is $2^n \mathit{poly}(n)$. Next, since $\log s = n^{o(1)}$, also $O(\log s) = n^{o(1)}$ (since constants are $n^{o(1)}$) and $O(\log s)^c = n^{o(1)}$ (since a constant multiple of $o(1)$ is also $o(1)$), hence the ...


1

If you care about the actual sizes, you need to keep the $n$. You could switch to $O((n+1)!)$ if that is easier for you. But maybe you only actually care about how fast the logarithm grows, and $\log(n!) = O(\log (n \cdot n!))$.


1

The function $n! \cdot n$ grows faster than $n!$, so it is not the case that $n! \cdot n$ is $O(n!)$. Therefore if all you know about an algorithm is that it runs in time $O(n! \cdot n)$, you cannot conclude that it runs in time $O(n!)$. What you can do is "O tilde" notation, and write $\tilde{O}(n!)$. The meaning of "O tilde" is not completely standard, so ...


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