Big-M Notation

Today's node.js chaos seemed like it was only a simple lesson in Operations 101 (hint: always host the code for your application and the modules it depends on in the same place) until one looks at the actual function that everyone was linking to:

function leftpad (str, len, ch) {
  str = String(str);

  var i = -1;

  if (!ch && ch !== 0) ch = ' ';

  len = len - str.length;

  while (++i < len) {
    str = ch + str;
  }

  return str;
}

This is quite possibly the worst algorithm in the (admittedly short) history of padding strings. Unless JS is doing something special behind our backs, we're looking at something on the order of len string allocations here, each one slightly larger than the last.

OK, so JS more or less asks for problems like this because it refuses to provide anything remotely resembling a standard library. Still, this is a common enough problem: people using dynamic memory management as if it were free, with no awareness of the costs of memory allocation and subsequent garbage collection.

To help raise awareness, I propose a Big-M notation to supplement Big-O notation (and Big-theta and all that). Big-M, or M( ), determines how memory allocations in an algorithm will grow with an input n. As with the other Big-notations, lower-order terms are dropped. 

Using this notation, the above string padding algorithm is M(n), when it should be something constant like M(1).