关于函数g(n)与f(n)关系判断的推理正确性验证

1. 𝑓=5𝑛+1，𝑔=10𝑛+30的推理验证 #

结论正确，但推理过程不严谨。
原推理仅验证了n=2时的单个情况，不符合大O符号的严格定义：大O符号要求存在常数c>0和n₀≥0，使得对所有n≥n₀，都有f(n)≤c·g(n)，不能只靠单个n值佐证。
正确证明：
我们可以取c=0.6，n₀=1。当n≥1时：
5n+1 ≤ 5n + n = 6n（因为n≥1时1≤n）
而10n+30 ≥10n，因此6n ≤0.6×10n ≤0.6×(10n+30)
即对所有n≥1，5n+1 ≤0.6×(10n+30)，完全满足大O定义，故f=O(g)成立。

2. 𝑓=𝑛ⁿ，𝑔=2ⁿ的推理验证 #

原推理结论和理由完全错误。
实际情况是：当n≥3时，nⁿ >2ⁿ（比如n=3时，3³=27>8=2³；n=4时，4⁴=256>16=2⁴），且nⁿ的增长速度远快于2ⁿ。
正确结论：g=O(f)，但f∉O(g)。

• 证明g=O(f)：取c=1，n₀=1，对所有n≥1，2ⁿ ≤nⁿ，满足大O定义。
• 证明f∉O(g)：假设存在常数c>0和n₀≥0，使得对所有n≥n₀，nⁿ ≤c·2ⁿ，即n ≤2·c^(1/n)。当n>2c时，c^(1/n) <c^(1/(2c)) ≤2（对于c>0，c^(1/(2c))≤2），此时2·c^(1/n) <4，但n>2c≥2（c>0），当n≥4时，n>4>2·c^(1/n)，矛盾。因此不存在这样的c和n₀，故f不是O(g)。

内容的提问来源于stack exchange，提问作者liatkatz