Study with Open Mind
When studying mathematical proof techniques, I found that it is important to study with an open mind. To prove a statement, first it is important to clearly formulate a problem, and then to collect facts, and then to follow logic reasoning.
For example, assuming we want to prove log(n!) is O(nlogn). The problem is clear. The fact we can use is the definition of Big-O in addition to the problem formulation. The definition of Big-O indicates that to prove a function f(n)is O(g(n))we need find constants c>0(real number) and n_0>0(integer) such that f(n)<=c.g(n) when n>=n_0.
To conclude the result, we need find c and n_0 in order to apply the definition of Big-O, which should be the goal during our reasoning. Here is the sequence.
log(n!)
= log(1 * 2 *...*n)
= log1 + ... + logn
<=logn + ... + logn
= nlogn
Therefore, there exist c =1, when n>=1, log(n!) <= nlogn,
based on the definition of Big-O, log(n!) = O(nlogn).
For example, assuming we want to prove log(n!) is O(nlogn). The problem is clear. The fact we can use is the definition of Big-O in addition to the problem formulation. The definition of Big-O indicates that to prove a function f(n)is O(g(n))we need find constants c>0(real number) and n_0>0(integer) such that f(n)<=c.g(n) when n>=n_0.
To conclude the result, we need find c and n_0 in order to apply the definition of Big-O, which should be the goal during our reasoning. Here is the sequence.
log(n!)
= log(1 * 2 *...*n)
= log1 + ... + logn
<=logn + ... + logn
= nlogn
Therefore, there exist c =1, when n>=1, log(n!) <= nlogn,
based on the definition of Big-O, log(n!) = O(nlogn).
Comments