Mathematics algorithms - how can I solve and replace?
I cannot understand the basic math behind algorithms. For example, the question arises here:
If a
f (n) = O (g (n))
there is
f (n) * log (f (n) ^ c) = O (g (n) * log (g (n)))
?
How can I answer this question? From what I understand so far, f (n) = O (g (n)) only when g (n) <= c (g (n)) and c and n are non-negative. So I need to start hooking the values to the above, but how do I do that? Let's say if I chose c = 5 and n = 2, I would include values like f (2) * log (f (2) ^ 5) = 5 (g (2) * log (g (2))) Does this mean that the answer to the original question is wrong?
source to share
You can do it like this:
f(n) * log(f(n)^c) = c * f(n) * log(f(n)) = O(1) * O(g(n)) * log(O(g(n))) = O(1) * O(g(n)) * O(log(g(n))) = O(g(n) * log(g(n))
...
So, the answer to the question is correct. All you need here is the properties of the logarithm function.
There is one step that may not be clear here: why log(O(g(n))) = O(log(g(n)))
?
Evidence. If f(n) = O(g(n))
, then there is a constant C
such that for large enough n
f(n) <= C * g(n)
. Thus log(f(n)) <= log(C * g(n)) = log(g(n)) + log(C)
. We can use C2 = 2
and receive log(f(n)) <= C2 * log(g(n))
when large enough n
.
source to share
By f (n) = O (g (n)), you mean
there exists k such that f (n) <= kg (n) for some n> = N_1. ----- 1
which implies log (f (n) ^ c) & lt = log (k ^ c) + log (g (n) ^ c) <= K * log (g (n) ^ c) for n> = N_2 and for K = max {log (k ^ c), 2} ----- 2
which gives us the required answer by multiplying 1 & 2
f (n) * log (f (n) ^ c) = O (g (n) * log (g (n))).
source to share