prove of disprove f(n) = 0(g(n)) implies lg(f(n)) = O(1g(g(n))), where lg(g(n)) > 1 and f(n) ≥ 1 for all sufficiently large n.
时间: 2023-12-03 08:13:36 浏览: 37
We will prove that f(n) = O(g(n)) implies lg(f(n)) = O(lg(g(n))), which is a stronger result than the statement we are trying to prove.
Since f(n) = O(g(n)), there exist positive constants c and N such that f(n) ≤ c*g(n) for all n ≥ N. Taking the logarithm of both sides, we get:
lg(f(n)) ≤ lg(c*g(n))
Using the logarithmic property that lg(a*b) = lg(a) + lg(b), we can write:
lg(f(n)) ≤ lg(c) + lg(g(n))
Now, since lg(g(n)) > 1, we have:
lg(f(n)) ≤ lg(c) + lg(g(n)) ≤ 2*lg(g(n))
Therefore, we have shown that lg(f(n)) = O(lg(g(n))), which is the stronger result we wanted to prove.
相关问题
prove of disprove f(n) = O(g(n)) implies g(n) = O(f(n))
This statement is false.
To disprove it, we can provide a counterexample. Let f(n) = n and g(n) = n^2.
Then, f(n) = O(g(n)) because n <= n^2 for all n >= 1. However, g(n) = n^2 is not O(f(n)) because there does not exist a positive constant c such that n^2 <= c*n for all n >= 1.
Therefore, f(n) = O(g(n)) does not imply g(n) = O(f(n)).
prove or disprove:f(n) = O(g(n)) implies 2^f(n) = O (2^g(n))
Prove:
Assume that f(n) = O(g(n)), which means there exist constants C and n0 such that for all n≥n0, f(n) ≤ Cg(n). Then, we have:
2^f(n) = 2^(Cg(n))
= (2^C)^g(n)
Let's assume that there exist constants C' and n1 such that for all n≥n1, 2^f(n) ≤ C'2^g(n).
Then we have:
(2^C)^g(n) ≤ C'2^g(n)
Take the logarithm of both sides, we get:
g(n) * log(2^C) ≤ log(C') + g(n) * log(2)
Simplifying the above equation, we get:
g(n) ≤ (log(C') + C * log(2)) / (log(2^C))
As the right-hand side is a constant, there exists some n2 such that for all n≥n2 , g(n) ≤ (log(C') + C * log(2)) / (log(2^C)), which contradicts the initial assumption that f(n) = O(g(n)).
Therefore, 2^f(n) is not O(2^g(n)).
Hence, we have proved that f(n) = O(g(n)) does not imply 2^f(n) = O(2^g(n)).