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 Aug 22 '18 at 9:56
  • $\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 Aug 22 '18 at 9:58

$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:

| cite | improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.