Quiz on Asymptotic Notation and Recurrence Relations

We compare $n \log n$ and $n^{1.5} = n \cdot n^{0.5}$. Dividing both by $n$, we compare $\log n$ vs $n^{0.5}$ (or $\sqrt{n}$). Since any positive polynomial power grows faster than a logarithm, $\log n = o(n^{0.5})$, and thus $n \log n = o(n^{1.5})$, which implies $O(n^{1.5})$.

Dies ist eine Summe von Potenzen. Approximation durch Integral $\int_1^{\log n} x^{3.5} dx \approx [x^{4.5}]^{\log n} \approx (\log n)^{4.5}$.

This is the standard recurrence for algorithms like Binary Search. Applying the Master Theorem ($a=1, b=2, f(n)=1$), we have $n^{\log_2 1} = n^0 = 1$. Since $f(n) = \Theta(n^{\log_b a})$, this is Case 2, giving $T(n) = \Theta(\log n)$.

This is a standard result derived from Stirling's approximation ($n! \approx (n/e)^n \sqrt{2\pi n}$). Taking the log gives $\ln(n!) \approx n \ln n – n$, which is dominated by the $n \ln n$ term. Therefore, the growth is $\Theta(n \log n)$.

If $f(n) \leq cn$ for $n > n_0$, then squaring both sides (since functions are non-negative in complexity analysis) gives $(f(n))^2 \leq c^2 n^2$. Letting $k = c^2$, we see $(f(n))^2 \leq k n^2$, so it is $O(n^2)$.