Computational Symbols

O ("big-oh", "capital O"); ASCII: 79, Unicode: U+004F, HTML: O

1. Big-Oh notation (computational complexity): O(f(x)) denotes the asymptotic upper-bound on the runtime of function f(x), typically expressed in terms of the size n of the input x. For example, if x contains n elements and the worst-case runtime of f(x) is linear in the size of x, then O(f(x)) = n. If the worst-case runtime of f(x) is quadratic in the size of x, then O(f(x)) = n^2 (n-squared). [ref]

Ω ("omega", aka "weird O"); ASCII: 937, Unicode: U+03A9, HTML: Ω

1. Omega notation (computational complexity): Ω(f(x)) denotes the asymptotic lower-bound on the runtime of function f(x), typically expressed in terms of the size n of the input x. For example, if x contains n elements and the best-case runtime of f(x) is linear in the size of x, then Ω(f(x)) = n. [ref]

Θ ("theta", aka "O with line"); ASCII: 920, Unicode: U+0398, HTML: Θ

1. Theta notation (computational complexity): Θ(f(x)) denotes a tight bound on the asymptotic runtime of function f(x), typically expressed in terms of the size n of the input x. For example, if x contains n elements and the exact runtime (up to a constant factor) of f(x) is linear in the size of x, then Θ(f(x)) = n. [ref]