Plot of log₂ x

In mathematics, the binary logarithm (log₂ n) is the logarithm for base 2. It is the inverse function of 2ⁿ. Image File history File links Binary_logarithm_plot. ... Image File history File links Binary_logarithm_plot. ... Wikibooks Wikiversity has more about this subject: School of Mathematics Wikiquote has a collection of quotations related to: Mathematics Look up Mathematics in Wiktionary, the free dictionary Wikimedia Commons has media related to: Mathematics Interactive Mathematics Miscellany and Puzzles — A collection of articles on various math topics, with interactive Java... Logarithms to various bases: red is to base e, green is to base 10, and purple is to base 1. ... The binary or base-two numeral system is a system for representing numbers in which a radix of two is used; that is, each digit in a binary numeral may have either of two different values. ... In mathematics, an inverse function is in simple terms a function which does the reverse of a given function. ...

The binary logarithm is often used in computer science and information theory (where it is frequently written lg n), because it is closely connected to the binary numeral system. The number of digits (bits) in the binary representation of a positive integer n is the integral part of lg n + 1, i.e. Computer science - Wikipedia, the free encyclopedia /**/ @import /skins-1. ... Information theory is the mathematical theory of data communication and storage generally considered to have been founded in 1948 by Claude E. Shannon. ... The binary numeral system represents numeric values using two symbols, typically 0 and 1. ... This article is about the unit of information. ... In mathematics, the floor function is the function defined as follows: for a real number x, floor(x) is the largest integer less than or equal to x. ...

In information theory, the definition of the amount of self-information and information entropy involves the binary logarithm; this is needed because the unit of information, the bit, refers to information resulting from an occurrence of one of two equally probable alternatives. Within the context of information theory, self-information is defined as the amount of information that knowledge about (the outcome of) a certain event, adds to someones overall knowledge. ... Entropy of a Bernoulli trial as a function of success probability. ... The word unit means any of several things: Unit of measurement or physical unit, a fundamental quantity of measurement in science or engineering. ...

The binary logarithm also frequently appears in the analysis of algorithms. If a number n greater than 1 is divided by 2 repeatedly, the number of iterations needed to get a value at most 1 is again the integral part of lg n. This idea is used in the analysis of several algorithms and data structures. For example, in binary search, the size of the problem to be solved is halved with each iteration, and therefore roughly lg n iterations are needed to obtain a problem of size 1, which is solved easily in constant time. Similarly, a perfectly balanced binary search tree containing n elements has height lg n+1. To analyze an algorithm is to determine the amount of resources (such as time and storage) necessary to execute it. ... Flowcharts are often used to represent algorithms. ... A binary tree, a simple type of branching linked data structure. ... In computer science, binary search or binary chop is a search algorithm for finding a particular value in a linear array, by ruling out half of the data at each step. ... A binary search tree of size 9 and depth 3, with root 7 and leaves 4, 7 and 13. ...

However, the running time of an algorithm is usually expressed in big O notation, ignoring constant factors. Since log₂ n = (1/log_k 2)log_k n, where k can be any number greater than 1, algorithms that run in O(log₂ n) time also run in, say, O(log₁₃ n) time. The base of the logarithm in expressions such as O(log n) or O(n log n) is therefore not important. In other contexts, though, the base of the logarithm needs to be specified. For example O(2^{lg n}) is not the same as O(2^{ln n}) because the former is equal to O(n) and the latter to O(n^0.6931...). Big O notation is a mathematical notation used to describe the asymptotic behavior of functions. ...

Algorithms with running time n lg n are sometimes called linearithmic. Some examples of algorithms with running time O(lg n) or O(n lg n) are: In computer science, a function is called linearithmic if it is of the form n · log n  (i. ...

• average time quicksort
• binary search trees
• merge sort
• Monge array calculation

A easy way to calculate the log₂(n) on calculators that do not have a log₂-function is to use the natural logarithm ln (which is found on most calulators).
The formula for this is: log₂(n) = ln(n)/ln(2). Quicksort in action on a list of random numbers. ... A binary search tree of size 9 and depth 3, with root 7 and leaves 4, 7 and 13. ... In computer science, merge sort or mergesort is a sort algorithm for rearranging lists (or any other data structure that can only be accessed sequentially, e. ... In computer science, an m-by-n array of real numbers is a Monge array if for all i, j, k, l such that: and one obtains: So whenever we pick two rows and two columns of a Monge array and consider the four elements at the intersection points, the...

See also

• natural logarithm (base e),
• common logarithm (base 10)