4 ms·

Isn’t O(n) here relative to lines of code? So O(n) * k is just O(n^2)?

• bsder 7y ago
  Not necessarily. For example, you could have a register coloring algorithm that runs in O(n^2) time that has no relation to number of lines of code. It is not unusual to have some optimization pass that has quadratic worst-case behavior but much better average behavior that makes it worth it 99% of the time but 1% of the time goes pathological.
  • rat9988 7y ago
    May I ask what the n refers to then?
    • bsder 7y ago
      Um, anything internal to the compiler that it is allocating. It could be number of registers spilled (graph coloring algorithms are NP-complete but have useful heuristic solutions ... most of the time), number of macros allocated, loop iterations unrolled, etc. If any of those things has a quadratic (or worse(!)) behavior, they may make compile times blow up if you hit a pathological boundary condition. And, sometimes I might even want that quadratic behavior optimization. If I'm trying to squeeze every single byte out of a program because I am on a memory constrained system, I'm probably pretty happy to let the compiler churn for a couple of hours to crush my program into memory if it means I don't have to start rewriting code that is nominally correct and risk introducing bugs.