Not exactly. There's no "compile time" or whatever. The point is that the computational complexity characterizes the difficulty of mapping an input to an outp

Not exactly. There's no "compile time" or whatever. The point is that the computational complexity characterizes the difficulty of mapping an input to an output. Sorting a list can be done with lots of different algorithms; the obvious ones are O(n^2). But there exist O(n log n) algorithms, so the complexity of sorting is O(n log n) irrespective of whatever implementation you might imagine. That O(n log n) is true now and for all time.