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.


6

The function $n^{1/\log \log n}$ tends to infinity, since $$ n^{1/\log\log n} = e^{\log n/\log\log n}, $$ and $\log n/\log \log n \longrightarrow \infty$.


6

You should be very careful when summing up a variable number of terms in asymptotic notation, as the result actually depends on the hidden constants. Consider the following example: $f_i(n) = i\cdot n$ for all integers $i$ and $n$. Then, for any integer $i$, $f_i(n) \in O(n)$. If you are not careful, you could end up writing something like: $$\sum_{i=1}^n ...


5

From this post, you can approximate $\log(1+x)$ with $x$ for little values of $x$. Hence, $$ f(n) \sim \frac{1}{\frac{1}{2^n-1}} = 2^n-1 $$ Therefore, you can't find any constant $c$, such that $f(n) = O(n^c)$, as it is $\Theta(2^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.


2

In your last step, a contradiction is reached since (by L'Hopital) $$\lim_{n\to\infty}\frac{\log n}{\log\log n}=\lim_{n\to\infty}\frac{1/n}{1/(n\log n)}=\lim_{n\to\infty}\log n$$ and $\log$ is unbounded.


2

It is $O(n)$ and, more precisely, $\Theta(n)$. What might be confusing you is the fact that the length of the encoding of the parameter $n$ will only be $\Theta(\log n)$, meaning that the value of $n$ (and hence the space required by the function) is exponentially larger than the size of the input to function (i.e., the number of bits needed to represent $n$...


2

Try it like this: "we can pick a constant $C$ such that, for sufficiently large $n$, $T(n)$ will always be less than $Cf(n)$". Intuitively, this does indeed mean that lower-order terms and constant factors don't matter. Because lower-order terms stop mattering once $x$ gets sufficiently large, and constant factors can be cancelled out by an appropriate ...


1

Let us use the master theorem as stated on Wikipedia. Consider a recurrence $$ T(n) = aT(n/b) + f(n). $$ There are several cases to consider: If $f(n) = O(n^c)$ for $c < \log_b a$ then $T(n) = \Theta(n^{\log_b a})$. If $f(n) = \Theta(n^{\log_b a} \log^k n)$ for $k \geq 0$ then $T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$. If $f(n) = \Omega(n^c)$ for $c >...


1

There isn't an error. You supposed that $n^{1/\log\log n}$ is constant and you derived the contradiction that $\log n/\log\log n$ is constant. Therefore, your supposition must be false. It would have been better to have written that $n^{1/\log\log n}\leq c$ for all $n$, since you're really trying to show that the function is bounded above by a constant,...


1

To express the sum over k in big o notation, use the formulae that express the sum of the $i$th powers of the first $n$ positive integers as a polynomial of degree $i+1$. For example, $\sum_{k=1}^n k$ is the quadratic function $n(n+1)/2 = O(n^2)$. The sum $\sum_{k=1}^n k^2$ is a cubic polynomial in $n$ and hence is $O(n^3)$, etc.


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