Hi, Math01-ga:
The essence of this problem is to show that (for sufficiently large n
or m), the expressions log(m) and log(n) are within a constant
multiple of one another.
Thus if something over log(m) is bounded (as m goes to infinity), the
same is true of that expression over log(n) (as n goes to infinity).
We will give a very detailed demonstration of this, but it is good to
keep the overall goal in mind as we proceed.
Formally O(log(m)) is a set, namely sequences indexed by m (or
functions of m, for notational convenience) such that the ratio upon
division by log(m) remains bounded as m goes to infinity.
Likewise O(log(n)) is a set of "expressions" dependent on n whose
ratio to log(n) remains bounded as n goes to infinity. Thus a claim
that O(log(m)) "is" O(log(n)) can be properly treated as an equality
of sets, meaning that each set is contained in the other.
As I already showed on another problem, in order for a graph with n
vertices to be connected m must be at least n-1.
On the other hand a simple graph (no multi-edges) can have at most
n(n-1)/2 edges (or, n(n+1)/2 if self-edges are allowed).
Thus n-1 <= m <= n(n+1)/2,
and since for all n > 2:
n/2 < n-1
n(n+1)/2 < n^2
we have for sufficiently large n:
n/2 < m < n^2
log(n) - log(2) < log(m) < 2 log(n)
because the logarithm function is strictly increasing.
It is already clear that any expression g(m) which is O(log(m)), i.e.
g(m)/log(m) is bounded by a constant C for all sufficiently large m
then g(m)/log(n) is bounded by twice that constant:
g(m)/log(n) = 2g(m)/(2 log(n)) < 2g(m)/log(m) <= 2C
because log(m) < 2 log(n) for sufficiently large n.
Thus O(log(m)) is contained in O(log(n)).
On the other hand, even if self edges are allowed, n > sqrt(m) for m >
2, so we can make n > K by restricting m > K^2. Then the condition
where we say n > 4, so that:
log(n) > log(4) = 2 log(2)
log(n)/2 > log(2)
log(n) - log(2) > log(n)/2
is implied by restricting m > 16.
Hence if an expression f(n) is O(log(n)), i.e.
f(n)/log(n) is bounded by a constant C' for all sufficiently large n
then f(n)/log(m) will be bounded by twice that constant:
f(n)/log(m) = 2f(n)/(2 log(m)) < 2f(n)/log(n) <= 2C'
because log(n)/2 < log(n) - log(2) < log(m),
and hence log(n) < 2 log(m).
This finally proves O(log(n)) contained in O(log(m)), so these sets
are equal.
regards, mathtalk-ga |
