Because the length of an item does not depend on the number of items to be sorted. The two are independent variables. In general, it's O(n * m). However, m is generally ignored because for any given task, it's general.
If we didn't ignore variables that are generally constant for a given case, O() notation would get excessively krufty. For example, the speed of all sorts is also proportional to the average length of identical prefixes for a pair of input strings - eg, how much has to be compared before finding a mismatch, on average. That's not included in big-O notation because it's generally constant for any one situation. |
