Θ
or Θ(f(n))
is often defined in terms of O(f(n))
or Ω(f(n))
. Other answers on this site define Θ(f(n))
in this way. What is the definition of Θ(f(n))
without using O
or Ω
?
Of course, since it is true that g(n) = Θ(f(n))
iff g(n) = O(f(n))
and g(n) = Ω(f(n))
, the definition of Θ(f(n))
without using O
or Ω
will still mirror the definitions of O
and Ω
in some way.
The function h(n)
is in Θ(k(n))
if there are positive numbers p
and q
such that beyond a some value of n
, h(n)
≤ p * k(n)
and h(n)
≥ q * k(n)
.