True or false with Big O Notation,

Question

1. True or false:

a. 14n + 12n^2 + 4 ∊ O(n^2 )

b. n^n ∊ O(2^n )

c. n log₂ n ∊ O(n log₅ n)

d. n log^2 n ∊ O(n log n)

e. 9n / (3 log n) ∊ O(n)

Note: log^k n = (log n)^K

Answer 1

1a. Notice how the highest order term is an n^2 term, therefore it is in the O(n^2). The formal way of realizing this is that for c = 13 and N = 15 then for n >= N it is true that 14n + 12n^2 + 4 <= cn^2.

1b. Notice how you have a variable to a variable power vs a constant to a variable power, the variable will always win out eventually. So n^n is not O(2^n).

1c. Remember changing of logarithm bases is simply dividing by a logarithm of a constant, so log_2(n) = log_5(n)/log_5(2) so for c = 1/log_5(2) we get for N >= 1 that nlog_2(n) = cnlog_5(n). Therefore since it is equal to, it is also clearly less than or equal to the value, so nlog_2(n) is O(nlog_5(n))

1d. nlog^2(n) has an extra strictly increasing variable (log(n)) multiplied by it, so a constant will never win out against it. For any c if N >= e^c then nlog^2(n) > nlog(n) so it is not O(nlog(n)).

e. If there we have a polynomial of a certain degree (degree one) divided by a strictly increasing function then that will be overtaken by a polynomial of the same degree by itself. So true, 9n/(3log(n)) is in O(n).

If you need more help, you can reach out to me!