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