Learn Before
Concept icon
Concept

Reading the parameter bounds as asymptotic statements

For nonnegative functions, f(n)=O(g(n)) means f(n)<=C*g(n) for some fixed C and all sufficiently large n. Theta means bounds in both directions. O_beta allows the constant and threshold to depend on the fixed integer beta, not on n. The notation poly lists parameters in which an upper bound is polynomial; it does not make a huge parameter small. Logs in this learning path are base two unless ln or exp is written; changing a fixed log base changes constants, not these orders. A bound 2^{o(n)} has an exponent divided by n tending to zero. It need not be useful at ordinary input sizes.

0

1

Concept icon
Updated 2026-11-08

Contributors are:

Who are from:

Tags

Math

Related
Related