Answer to Question #174226 in Algorithms for Jean Claude

Question

The performance of an algorithm can be determined in terms of its time and space complexity. Explain the difference between time complexity and space complexity and make a case for which is the most efficient method for determining the performance of an algorithm

Answer 1

Time complexity is a function describing the amount of time an algorithm takes in terms of the amount of input to the algorithm.

Space complexity is a function describing the amount of memory (space) an algorithm takes in terms of the amount of input to the algorithm.

Example: Selectiom Sort

The amount of space needed is clearly dominated by the memory consumed by the array, so we don't have to worry about it; if we can store the array, we can sort it. That is, it takes constant extra space.

So we are mainly interested in the amount of time the algorithm takes. One approach is to count the number of array accesses made during the execution of the algorithm; since each array access takes a certain (small) amount of time related to the hardware, this count is proportional to the time the algorithm takes.