edited by
284 views
2 votes
2 votes

If F(n) = (log n)then, is F(n) = O(n2) true?

Also, what about F(n) = $\Theta$(n2)

edited by

1 Answer

Best answer
1 votes
1 votes

Let us assume that $F(n) = O(n^2)$ is true. Then for some positive integer $c_1$

$$(log_2(n))^n \leqslant c_1n^2 \\ (nlog_2log_2(n)) \leqslant 2c_1log_2(n)$$

However, for very large value of $n$ there do not exist a positive integer $c_1$ for which this equality holds true. Therefore, our assumption $F(n)=O(n^2)$ must be false.

$F(n) = \theta(n)$ if and only if $F(n) = O(n)$ and $F(n) = \Omega(n))$. And since we have proved that $F(n) \neq O(n)$ therefore, $F(n) \neq \theta(n)$


Here I present a intuitive reason of why $(nlog_2log_2(n))$ is not bounded by $log_2(n)$.

For very large value of $n$ the value of $log_2log_2(n)$ will be very small. Thus the growth rate of $(nlog_2log_2(n))$ will be slightly greater than (or almost equal to) that of $n$. However, at the same time the growth rate of $log_2(n)$ will be very small as compared to $n$. Thus, $log_2(n)$ cannot bound $log_2log_2(n)$.

You can see how these two functions grow with $n$ here on this link: https://www.desmos.com/calculator/phyrvzmdu6

selected by

No related questions found