A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

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

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