Bit complexity is the number of elementary operations on bits required by an algorithm, measured as a function of the input length in bits in a specified model of computation. Computation time measured in bit operations is also called bit time.

The cost of arithmetic on integers depends on their bit length. Using for big-O notation, the usual addition of two -bit integers uses bit operations. Counting each addition, subtraction, or multiplication as a single operation regardless of operand length gives a different cost model (Brent and Zimmermann 2010, pp. 2-4).

See also

Bit, Bit Length, Computation Time, Computational Complexity, Polynomial Time, Quasipolynomial Time, Strassen Formulas, Superpolynomial Time

Explore with Wolfram|Alpha

References

Borodin, A. and Munro, I. The Computational Complexity of Algebraic and Numeric Problems. New York: American Elsevier, 1975.Brent, R. P. and Zimmermann, P. Modern Computer Arithmetic. Cambridge, England: Cambridge University Press, 2010. https://doi.org/10.1017/CBO9780511921698.

Referenced on Wolfram|Alpha

Bit Complexity

Cite this as:

Weisstein, Eric W. "Bit Complexity." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/BitComplexity.html

Subject classifications