关于Big-O，Theta和Omega符号的两个问题

Question

证明或反驳以下声明：

1. 存在功能f(n)所以f(n-k)不等于Big-theta (f(n))。当k>=1并且是正常数。

这个说法是真的有什么功能吗？我想到了f(n)=n!，但我不确定这是正确的答案。此外，如果f(n)=n!是正确的，如何证明这种说法？

2. 存在功能所以(f(n))^2=Big-O(f(n))和f(n)=Big-omega (log(log(n)))。

我认为没有任何功能可以宣称这是真的。如果这是正确的 - 如何证明？

Answer 1

1. 正确的f（n）= n！。足以表明对于任何固定的k> = 1，（n - k）！不是Omega（n！），对于任何常数c> 0，它适用于所有n足够大的c * n！ >（n - k）！
2. 没有f（n）使得f（n）^ 2 = O（f（n））和f（n）= Omega（log log n）。后者意味着对于某些常数c> 0且所有n足够大，f（n）> c log log n，特别是对于所有n足够大的f（n）> 1。如果我们现在假设f（n）^ 2 = O（f（n）），则存在一个常数r> 0，因此对于所有n足够大，f（n）^ 2 <r * f（n），即f（n）<r。但是这意味着所有n的log log n <（r / c）足够大，对于所有n> e ^（e ^（r / c））（其中e是log的基础）是假的。