In computer science, the complexity function of a word or string (a finite or infinite sequence of symbols from some alphabet) is the function that counts the number of distinct factors (substrings of consecutive symbols) of that string.
More generally, the complexity function of a formal language (a set of finite strings) counts the number of distinct words of given length.
Define the function pu(n) of a positive integer n to be the number of different factors (consecutive substrings) of length n from the string u.
For example, it may be bounded but not eventually constant: the complexity function of the regular language
[19] The topological entropy of an infinite sequence u is defined by The limit exists as the logarithm of the complexity function is subadditive.
[20][21] Every real number between 0 and 1 occurs as the topological entropy of some sequence is applicable,[22] which may be taken to be uniformly recurrent[23] or even uniquely ergodic.
[6] It is conjectured that for algebraic irrational x the complexity is bn (which would follow if all such numbers were normal) but all that is known in this case is that p grows faster than any linear function of n.[25] The abelian complexity function pab(n) similarly counts the number of occurrences of distinct factors of given length n, where now we identify factors that differ only by a permutation of the positions.