4 ms·

OK, so he has a concept of a time when the program is written and so on. Decisions about how the program is written, or what is to be written, can involve non-c

• evanb 2y ago
  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.
  • kazinator 2y ago
    > computational complexity characterizes the difficulty of mapping an input to an output The question revolves around computability: can the input be mapped to an output; does the calculation terminate and the output emerge.