0
$\begingroup$

When I am trying to show whether or not the following statements about the Big Oh complexity of the functions below are true or false, am I eliminating too many terms from the function? I want to make sure I am only eliminating the appropriate lower order terms and constant coefficients.

On a related note, is there a distinction between eliminating lower order terms and constant coefficients and using log rules to get the expression to equal $n^3$, for example, and it being $O(n^3)$?

a) $3 n^{2} \log_{2} n + 16 n \mbox{ is } O(n^{3}).$ False.

Begin by eliminating both $16n$ because is is a lower order term and the 3 preceding the first term because it is a constant coefficient. You are left with $n^{2} \log_{2} n.$ Using the change of base formula, this can be simplified to$\frac{n^2 log_{10}(n)}{log_{10}(2)},$ which equals $\frac{1}{log(2)} \times n^2 log_{10}(n).$ $\frac{1}{log(2)}$ can be eliminated because it is a constant coefficient, so you are left with $n^2 log_{10}(n).$ Compared to $n^2,$ $log_{10}(n)$ is insignificant and can be eliminated. Thus, $3 n^{2} \log_{2} n + 16 n \mbox{ is not } O(n^{3}),$ but rather $O(n^2)$.

b) $25 \log_{2} 8n^{10} \mbox{ is } O(\log_{10} n)$. True.

Begin by eliminating $25$ because it is a constant coefficient. You are left with $\log_{2} 8n^{10}.$ By the change of base formula, this can be simplified to $\frac{log_{10}(8n^{10})}{log(2)},$ which equals $\frac{1}{log(2)} \times log_{10}(8n^{10}).$ $\frac{1}{log(2)}$ can be eliminated because it is a constant coefficient, so you are left with $log_{10}(8n^{10}).$ Because $8$ is a constant coefficient, it can also be eliminated to give $log_{10}(n^{10}).$ According to the power rule, this is equal to $10 log_{10}(n).$ Now, the $10$ can be eliminated because it is a constant coefficient, and only $log_{10}(n)$ remains. Thus, $25 \log_{2} 8n^{10} \mbox{ is } O(\log_{10} n)$.

c) $8^{\log_{2} n} \mbox{ is } O(n^{3})$. True.

According to the rule $a^{log_b n} = n^{log_b a}$, $8^{\log_{2} n} = n^{\log_{2} 8}.$ Because $log_2 8 = 3, n^{\log_{2} 8} = n^3.$ Thus, $8^{\log_{2} n} \mbox{ is } O(n^{3}).$

$\endgroup$
  • 1
    $\begingroup$ You can not elimnate insignificant factors from a product. $n^2 \log n > n^2$. You can only eliminate summands, if they are lower. If you were able, you could argue that $n^10=n^9\cdot n =\mathcal{O}(n^9)$ since the last $n$ is insignificant. Also: $\mathcal{O}(n^3)$ are all functions, that don't grow faster, than $n^3$. So $n^2 \log n$ is in $\endgroup$ – Laray Sep 11 '17 at 7:44
  • $\begingroup$ When you use the big Oh notation, you need to specify which was $n$ tends. In this case, it seems like you mean to talk about $n \rightarrow \infty$. The other thing I'd like to mention is that $\mathcal{O}(1) < \mathcal{O}(\log n) < \mathcal{O}(n)$ as $n \rightarrow \infty$. For example, $\mathcal{O}(n^2) < \mathcal{O}(n^2 \log n) < \mathcal{O}(n^3)$. So you immediately know you can drop the second term in your example a. $\endgroup$ – Mathemagical Sep 11 '17 at 8:32
  • $\begingroup$ @Laray Thanks for the clarification! So for a), would if simply be $O(n^2 log_{10} n)$ or does it somehow simplify to $O(n^3)$? $\endgroup$ – fs24 Sep 11 '17 at 14:55
  • $\begingroup$ You can drop the 10 in the log-Base, since (as you already did) logarithms are equal to a constant factor, that is dropped in $\mathcal{O}$. $\endgroup$ – Laray Sep 12 '17 at 10:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.