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)).
-
$\begingroup$ You are asking for the definition, which can be found in any resource. If you want some intuition, there's an older question with good answers. $\endgroup$Raphael– Raphael2018年08月22日 09:56:38 +00:00Commented Aug 22, 2018 at 9:56
-
1$\begingroup$ "An algorithm is in the complexity class Θ(f(n))." -- that's not something we would say because it doesn't type check. 1) $\Theta(f)$ is not a complexity class (which is a set of problems), it's a class of functions. 2) Algorithms are contained in neither. $\endgroup$Raphael– Raphael2018年08月22日 09:58:41 +00:00Commented Aug 22, 2018 at 9:58
1 Answer 1
$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))$.
Useful links: