3.4 Algorithmic Complexity

The complexity of algorithms is often described in big-O notation, a shorthand for the asymptotic behavior of the algorithm. For example, searching for a name in a phone book by starting at the beginning and going name-by-name takes on average, n/2 operations, where n is the number of names in the phone book. Such a search has O(n) time complexity (constants are dropped from the notation). It scales linearly in time; a phone book twice as long takes twice as long to search. An approach that scales more efficiently successively splits the phone book in half based on the alphabetical order. This is called a binary search and has O(log₂n) complexity. For example, a phone book eight times longer takes only three times longer to search. The alignment algorithms as described have O(nm) complexity in both time and memory, where n and m are the lengths of the sequences. It's also common to label such algorithms as O(n2) and speak of them as scaling quadratically.