complexity function

Definitions

1. 1

   A function that counts the number of distinct factors (substrings of consecutive symbols)…

   A function that counts the number of distinct factors (substrings of consecutive symbols) in a string of symbols;

   • It follows that #92;bullet The length function l#58;A#42;#92;longrightarrow#92;mathcalN is a complexity function on A#42;.
2. 2

   A function representing the computational complexity an algorithm.

   • A complexity function need not have a quadratic term to be in O(n²). It need only eventually lie beneath some pure quadratic function on a graph. Therefore, any logarithmic or linear complexity function is in O(n²).
   • Hence, the worst case time complexity function of Floyd's algorithm is O(n³).

The neighborhood