This question already has an answer here:

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


marked as duplicate by Raphael Aug 22 '18 at 9:57

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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


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