calculate time/space complexity while running program

Question

I am trying different types of sorting algorithms and I understand the concept of asymptotic time and space complexity.

I am wondering whether we can write some logic in the program itself to calculate the space/time complexity of that algorithm so that we can have a proof that the algorithm behaves as expected?

Does anyone have any thoughts on this?

Answer 1

With instrumentation you can only measure the time and space used for a specific instance of a problem. Only if you were to enumerate all possible problem instances you'd be able to proof the worst case time and space complexity. In practice this is rather indefeasible.

You'd need to enumerate all possible instance because you don't know which inputs will be hard and which will be easy. For example if you were to test BubbleSort with ordered inputs from 1...n with varying length, you'd never observe the worst case.