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_{2}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.