Search code examples
time-complexitybig-ocomplexity-theorydefinitionfunction-definition

What is the formal definition of Θ(f(n)) without expressing Θ(f(n)) in terms of O(f(n)) or Ω(f(n))?


Θ 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.


Solution

  • 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).