On writing proofs about asymptotic relationsPrepared by Hung Q. Ngo∗January 24, 2007In this document, I formally write a few things discussed in previous lectures. Most problems arefirst analyzed in a draft form, indicating how I think about the solution to the problem. Then, formalproofs are presented. When writing homework solutions, only formal proofs are required.Problem 1. Given two functions f, g : N+→ R+such that both f (n) and g(n) tend to ∞ as n → ∞,is it true that lg(f (n)) = O(lg(g(n)) implies f (n) = O(g(n))?Informal analysis. The value lg(f(n)) roughly is the “power part” of the function f (n). If f (n) = n3,then lg(f (n)) = 3 lg n. The relation lg(f(n)) = O(lg(g(n)) says that the power-part of f (n) is upperbounded by some constant times the power-part of g(n). Hence, it is possible that lg(f (n)) is greaterthan lg(g(n) by a constant factor, yet the relation lg(f (n)) = O(lg(g(n)) still holds. For instance,f(n) = n100, g(n) = n1, i.e. lg(f(n)) = 100 lg(g(n)), yet lg(f(n)) = O(lg(g(n)). However, clearlyn1006= O(n). This is a perfect counter example to the claim!Formal proof. NOT TRUE. Take, for instance, f(n) = n100, g(n) = n. Then, lg(f (n)) = 100 lg n =O(lg(n)), yet n1006= O(n).Note again: a formal proof is all we need for homework problems. Do not go at length explainingyour thinking!Problem 2. Given two functions f, g : N+→ R+such that both f (n) and g(n) tend to ∞ as n → ∞,is it true that lg(f (n)) = o(lg(g(n)) implies f (n) = o(g(n))?Informal analysis. In Problem 1, the assertion was not true because the O relation is not very strong:f could be O(g) even though f is a constant factor greater than g. The o relation, however, indicatesthat the power-part of g grows infinitely faster than the power-part of f. It only makes sense then, that ggrows infinitely faster than f.How are we going to prove something like this? Let’s start from the definitions.What we know is: lg(f (n)) = o(lg(g(n)), which, by definition, means that for all c > 0, lg(f (n)) ≤c lg(g(n)) for large enough n (say n ≥ n0, for some n0).What we want is: for all ¯c > 0, f (n) ≤ ¯cg(n) when n ≥ n1, for some n1.Let’s start from what we want to prove, to see what it is equivalent to, at the same time try to make aconnection to what we know. Consider any constant ¯c > 0.f(n) ≤ ¯cg(n) ⇔ lg(f(n)) ≤ lg(g(n)) + lg(¯c).The reason we want to take lg is clear: what we know involves the lg of the two functions!Now, for any constant c,lg(f (n)) ≤ c lg(g(n)), for n ≥ nc. (1)∗Please let me know of any mistakes/typos as soon as you find them1How do we use this to showlg(f (n)) ≤ lg(g(n)) + lg(¯c), for large enough n. (2)It is only natural to pick c > 0, so thatc lg(g(n)) ≤ lg(g(n)) + lg(¯c), (3)in which case (3) and (1) imply (2)!When lg(¯c) ≥ 0, we can pick c = 1 and (3) would definitely hold.When lg(¯c) < 0, (3) is equivalent toc lg(g(n)) ≤ lg(g(n)) + lg(¯c)− lg(¯c) ≤ (1 − c) lg(g(n))We thus have to choose c so that 1 − c > 0, in which case the last inequality is the same as− lg(¯c)1 − c≤ lg(g(n)),or2− lg( ¯c)1−c≤ g(n).This is definitely true since the left hand side is a constant (for a fixed ¯c and a constant c < 1 we havechosen), while g(n) was assumed to go to ∞. (This is true for n is large enough!)Formal proof. We want to show that, for any ¯c > 0, there is some constant n0such that f (n) ≤ ¯cg(n)when n ≥ n0.Consider any ¯c > 0.Case 1: ¯c ≥ 1, or lg( ¯c) ≥ 0.Since lg(f (n)) = o(lg(g(n)), by definition there is some n1such thatlg(f (n)) ≤ 1 · lg(g(n)) for all n ≥ n1.Thus,lg(f (n)) ≤ lg(g(n)) + lg(¯c), ∀n ≥ n1,which is equivalent tof(n) ≤ ¯cg(n), ∀n ≥ n1.Hence, when ¯c ≥ 1, we can pick n0= n1, and our assertion is proved.Case 2: 0 < ¯c < 1, or lg(¯c) < 0.Since lg(f (n)) = o(lg(g(n)), by definition there is some n1such thatlg(f (n)) ≤12· lg(g(n)) ∀n ≥ n1.Since limn→∞g(n) = ∞, there is some n2such that2− lg( ¯c)1/2≤ g(n), ∀n ≥ n2.Now, pick n0= max{n1, n2}, we have, for all n ≥ n0,2− lg( ¯c)1/2≤ g(n)⇔ − lg(¯c) ≤12lg(g(n))⇔12lg(g(n)) ≤ lg(¯c) + lg(g(n)) = lg(¯c · g(n)).2Consequently, for all n ≥ n0, we havelg(f (n)) ≤12· lg(g(n)) ≤ lg(¯c · g(n)),which is the same asf(n) ≤ ¯c · g(n), ∀n ≥ n0,as