f（n）=Θ（f（n））是真的吗？(Is it true that f (n) = Θ(f (n))?)

f（n）=Θ（f（n））是真的吗？(Is it true that f (n) = Θ(f (n))?)

你能证明使用f（n）等于大Theta（f（n））的反身性吗？ 考虑它时似乎很直接，因为f（n）本身就在上下。 但是我怎么写这个呢？ 这适用于大型欧米茄和大型O.

Can you prove using reflexivity that f(n) equals big Theta(f(n))? It seems straight forward when thinking about it because f(n) is bounded above and below by itself. But how will I write this down? And does this apply to big Omega and big O

最满意答案

我相信你想要问的是（wrt @emory：s的答案）是有道理的：

“对于某些函数f(n) ， f ∈ ϴ(f(n))是真的吗？”

如果你从Big-Θ符号的正式定义中发出，很明显这是成立的。

---

f ∈ ϴ(g(n))

⇨对于某些正常数c1 ， c2和n0 ，以下成立：

c1 · |g(n)| ≤ |f(n)| ≤ c2 · |g(n)|, for all n ≥ n0 (+)

设f(n)为任意实值函数。 设置g(n) = f(n)并选择例如c1=0.5 ， c2=2和n0 = 1 。 然后，自然地， (+)成立：

0.5 · |f(n)| ≤ |f(n)| ≤ 2 · |f(n)|, for all n ≥ 1

因此， f ∈ ϴ(f(n))成立。

I believe what you are intending to ask is (w.r.t. @emory:s answer) is something along the lines:

"For some function f(n), is it true that f ∈ ϴ(f(n))?"

If you emanate from the formal definition of Big-ϴ notation, it is quite apparent that this holds.

---

f ∈ ϴ(g(n))

⇨ For some positive constants c1, c2, and n0, the following holds:

c1 · |g(n)| ≤ |f(n)| ≤ c2 · |g(n)|, for all n ≥ n0 (+)

Let f(n) be some arbitrary real-valued function. Set g(n) = f(n) and choose, e.g., c1=0.5, c2=2, and n0 = 1. Then, naturally, (+) holds:

0.5 · |f(n)| ≤ |f(n)| ≤ 2 · |f(n)|, for all n ≥ 1

Hence, f ∈ ϴ(f(n)) holds.