Time space trade off
The problem of trade off arises as time and memory space are costly and
resources which have to be minimized. If sufficient storage space is available,
optimum results will be obtained to use a algorithm using more space and less
time. On the other hand if processing of a program requires huge time, it would
be economical to use an algorithm involving more time and less space trade-off
between time and space will be required till a continuous efficiency in
performance in attached. So the space-time tradeoff refers to a choice between
algorithmic solution of a data processing problem that allows one to decrease
the running time of an algorithmic solution by increase the space to store the
data and vice versa.
Time complexity is commonly estimated by counting the number of elementary
operations performed by the algorithm, where an elementary operation takes a
fixed amount of time to perform. Thus the amount of time taken and the number
of elementary operations performed by the algorithm differ by at most a constant
Since an algorithm’s performance time may vary with different inputs of the same
size, one commonly uses the worst-case time complexity of an algorithm,
denoted as T(n), which is defined as the maximum amount of time taken on any
input of size n. time complexities are classified by the nature of the function T(n).
for instance, an algorithm with T(n) = O(n) is called a linear time algorithm, and
an algorithm with T(n – O(2^n)) is said to be an exponential time algorithm.