Plugin for replacing text with HTML
I would think that a major time complexity comes from the usage of Regex which involves 'steps' in the processing of the expression, meaning the complex the statement, the more steps it can take.

Instead of using a Regex for when settings.globally is false, a normal String.replace can be done.

And instead of using a Regex for the global checks, I would suggest using a String.prototype.replaceAll polyfill like the following:

String.prototype.replaceAll = function(search, replace){
    var string = this;
    var index = 0;
    while ((index = string.indexOf(search)) !== -1) {
        string = string.replace(search, replace);
    }
    return string;
}


Which would change the settings.globally block into:

if(settings.globally) {
    $(node).replaceWith(text.replaceAll(settings.textToReplace, settings.replaceWithText));
} else {
    $(node).replaceWith(text.replace(settings.textToReplace, settings.replaceWithText));
}


I would also suggest removing jQuery from the solution as well. extend, $ (the element fetching), match and each can be polyfilled in, or simply converted to vanilla JavaScript.

function $(selector, el) {
    if (!el) { el = document; }
    return Array.prototype.slice.call(el.querySelectorAll(selector));
}
var extend = function(out) {
  out = out || {};
  for (var i = 1; i &lt; arguments.length; i++) {
    if (!arguments[i])
      continue;
    for (var key in arguments[i]) {
      if (arguments[i].hasOwnProperty(key))
        out[key] = arguments[i][key];
    }
  }
  return out;
};
if (!String.prototype.includes) {
  String.prototype.includes = function() {'use strict';
    return String.prototype.indexOf.apply(this, arguments) !== -1;
  };
}


and for each: you can use Array.prototype.forEach (The polyfill is quite large, so I didn't include it) or a simple for loop.