Time compexity is(roughly speaking) how the algorithm behaves as the input increases. Something with time complexity O(n) will take twice the time when the input doubles, something with time complexity O(N^2) will take four times longer when the input duobles and so on.
Space complexity is the storage required for the execution of the algorithm. This includes all permanent and temporary storage required by the algoritm, including any necessary stakc allocations for recursions,
If we look at three different implementations of the Fibonacci algorithm, one straight-forward recursive implementation, one iterative and one recursive memoised version, we can compare and contrast different trade-ofsf between time and space complexity.
First, the straight-forward recursive algorithm:
(defun fib (n)
(cond ((< n 2) n)
(t (+ (fib (- n 1)) (fib (- n 2))))))
The space complexity is O(n), mostly taken up by stack
allocations. The time complexity is O(fib(n+1)), this is approximately
O(e^n). Not the best performer in the world.
Next, we look at an iterative version.
(defun fib (n)
(let ((a 0)
(b 1))
(dotimes (i n) (psetf a (+ a b) b a))
a))
The time complexity has gone down to O(n) and the space complexity is
down to O(1). Probably a good choice for most cases and still pretty
straight-forward to analyse.
Last, we have the memoised Fibonacci:
(let ((memo (make-hash-table)))
(setf (gethash 0 memo) 0)
(setf (gethash 1 memo) 0)
(defun fib (n)
(let ((lookup (gethash n memo)))
(cond (lookup lookup)
(t (fib (- n 1) (fib (- n 2))))))))
This one is interesting. Space complexity is back up to O(n)
(essentially, each computed value will take up constant space in the
lookup table). However, run-time complexity is a bit harder to
compute, but by looking carefully at what the algorithm does, we can
see that the first time fib(n) is computed, it will have an O(n)
ruintime, but then have an O(1) run-time. If we are computing a lot of
Fiboniacci values, we will see an amortised run-time complexity of O(1).
This is one of Ingvar's essays