CODEWITHSUNDEEP
reflectiontime-complexitybig-o
Tomix
Tomix

Reputation: 3

Is it true that f (n) = Θ(f (n))?

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

Upvotes: 0

Views: 3763

Answers (2)

dfrib
dfrib

Reputation: 73236

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.

Upvotes: 1

emory
emory

Reputation: 10891

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.

Upvotes: 0

Related Questions