What would these statements mean if f(n) and g(n) are functions over natural numbers?
g(n) is in Θ(f(n)). and
An algorithm is in the complexity class Θ(f(n)).
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
$g(n)$ is in $O(f(n))$ means that there exists a positive number $c$ such that $g(n) \leq c \cdot f(n)$ for all $n$ (or at least all large $n$s). In other words, $g(n)$ does not grow faster than $cf(n)$.
We say "is in" because $O(f(n))$ is a class of all functions that satisfy above condition. It is also sometimes said just "is" and written $g(n) = O(f(n))$ but in my opinion this is too misleading because equality here is not symmetric.
That an algorithm is in a complexity class $O(f(n))$ means that a function $g$ that measures the number of basic calculation steps (dependant of the input size $n$) of this algorithm is in $O(f(n))$.