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
你能证明使用自反性f(n)等于大(f(n))吗?当我们考虑它的时候，它似乎是直接向前的，因为f(n)是由它自己上界和下界的。但是我该怎么写呢?这是否适用于大O
2 个解决方案
#1
1
I believe what you are intending to ask is (w.r.t. @emory:s answer) is something along the lines:
我相信你想问的是(w。r。t。@emory:s answer)。
"For some function
f(n), is it true thatf ∈ ϴ(f(n))?"“对于一些函数f(n),f真的∈ϴ(f(n))?”
If you emanate from the formal definition of Big-ϴ notation, it is quite apparent that this holds.
如果你是从Big-ϴ正式定义的符号,这很明显。
f ∈ ϴ(g(n))f∈ϴ(g(n))
⇨ For some positive constants
c1,c2, andn0, the following holds:⇨一些积极的c1,c2,n0,以下是适用的:
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:
让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
Hence, f ∈ ϴ(f(n)) holds.
因此,f∈ϴ(f(n))。
#2
0
No we can not because it is not true. ϴ(f(n)) is a set. f(n) is a member of that set. f(n)+1 is also a member of that set.
不，我们不能，因为那不是真的。ϴ(f(n))是一个集f(n)是集f(n)+ 1也是一个成员的集合。
#1
1
I believe what you are intending to ask is (w.r.t. @emory:s answer) is something along the lines:
我相信你想问的是(w。r。t。@emory:s answer)。
"For some function
f(n), is it true thatf ∈ ϴ(f(n))?"“对于一些函数f(n),f真的∈ϴ(f(n))?”
If you emanate from the formal definition of Big-ϴ notation, it is quite apparent that this holds.
如果你是从Big-ϴ正式定义的符号,这很明显。
f ∈ ϴ(g(n))f∈ϴ(g(n))
⇨ For some positive constants
c1,c2, andn0, the following holds:⇨一些积极的c1,c2,n0,以下是适用的:
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:
让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
Hence, f ∈ ϴ(f(n)) holds.
因此,f∈ϴ(f(n))。
#2
0
No we can not because it is not true. ϴ(f(n)) is a set. f(n) is a member of that set. f(n)+1 is also a member of that set.
不，我们不能，因为那不是真的。ϴ(f(n))是一个集f(n)是集f(n)+ 1也是一个成员的集合。