大西塔问题

Question

我有两个功能：

• F（N）= 2;
• g（n）= 10^100;

我必须证明如果f（n）= BigTheta（g（n））或不。我的猜测是f（n）是BigTheta（g（n）），因为这两个函数都是常量（这意味着函数是成比例的），但是我的老师坚持认为我错了。

我对不对？有什么方法可以让我的病情得到休息吗？ 对不起，如果这听起来像一个noob问题！谢谢。

Answer 1

f(n) <= g(n) * 1 
2 <= 10^100  for all n >= 0 

因此f(n) = O(g(n))。

f(n) >= g(n) * 2/(10^100) 
2 >= 10^100 * 2/(10^100) = 2  for all n >= 0 

等等f(n) = Ω(g(n))。

f(n)=O(g(n))和f(n)=Ω(g(n))暗示f(n) = Θ(g(n))。你是对的。

Answer 2

你是对的。假设你引用了正确的问题并且没有误解，如果你的老师说他们不是彼此之间的东西，那么你的老师是错误的。

这里的定义是：

http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations

显然|100^10|*k1 <= |2| <= |100^2|*k2常量k1=1/100^10和k2=1（对于所有x比任何合适的临界值x_cutoff大）

不知道考试问题的实际文本虽然，以及你写的（或圈出的）确切的文字，我们不可能在互联网上知道这个问题没有任何误解。你也应该注意到，即使你的回答是正确的，你仍然可能在错误的理由。

备案时，不仅是f(x)在集BigTheta(g(x))，但g(x)是在集BigTheta(f(x))。我认为一个等价的定义是，这两个函数的比率是有界的x -> infinity（通过将维基百科的定义除以|g(x)|得到|f(x)|/|g(x)| < constant经过某个分界点），这可能是一个更容易的定义要考虑（并且更明显证明）。这也意味着BigTheta是一个对称关系。

你现在有合适的工具来问“为什么你认为我错了？”然后用数学来确定你们哪一个是对的;任何误解都应该出现在数学中，如果不是的话，你会证明你的观点。