Algorithm Complexity
The time and space it uses are two major measures of the efficiency of an algorithm. The
complexity of an algorithm is the function which gives the running time and/or space in terms
of the input size.
Suppose X is an algorithm and n is the size of input data, the time and space used by the
algorithm X are the two main factors, which decide the efficiency of X
Time Factor - Time is measured by counting the number of key operations such as
comparisons
in the sorting algorithm.
Space Factor -Space is measured by counting the maximum memory space required by the
algorithm.
The complexity of an algorithm f(n) gives the running time and/or the storage space required
by the algorithm in terms of n as the size of input data.
Space Complexity
Space complexity of an algorithm represents the amount of memory space required by the
algorithm in its life cycle. The space required by an algorithm is equal to the sum of the
following two components
A fixed part that is a space required to store certain data and variables that are independent of
the size of the problem. For example, simple variables and constants used, program size, etc.
A variable part is a space required by variables, whose size depends on the size of the problem.
For example, dynamic memory allocation, recursion stack space, etc.
Space complexity S (P) of any algorithm P is
S (P)=C+SP (1)
Where,
C is the fixed part and
S (I) is the variable part of the algorithm, which depends on instance characteristic I.
Following is a simple example that tries to explain the concept -
Algorithm: SUM (A, B)
Step 1-START
Step 2-C-A+B+10
Step 3 - Stop
Here we have three variables A, B, and C and one constant. Hence S (P) = 1+3.
Now, space depends on data types of given variables and constant types and it will be multiplied
accordingly.
Time Complexity
Time complexity of an algorithm represents the amount of time required by the algorithm to
run to completion. Time requirements can be defined as a numerical function T (n).
Where,
T (n) can be measured as the number of steps, provided each step consumes constant time.
For example, addition of two n-bit integers takes n steps. Consequently, the total computational
time is
T (n) = c*n
Where,
c is the time taken for the addition of two bits.
Here, we observe that T(n) grows linearly as the input size increases.
Examples:
1. T(n)= 𝟐𝒏𝟐 +3n+1
• Drop lower order terms
• Drop all the constant multiplies.
T(n)=O(𝑛2 )
2. Loop
For( i=1; i<=n; i++)
{
X=y+z;// constant time (C)
T(n)=C(n)
T(n)=O(n)
3. Nested loop
For(i=1;i<=n;i++)
{
For(j=1;j<=n;j++)
{
X=y+z;// constant time (C)
T(n)=C(𝑛2 )
T(n)=O(𝑛2 )
Time-Space Trade-off
A time space trade-off is a situation where by increasing the amount of space for storing the
data, one may be able to reduce the time needed for processing the data, or vice versa
(conversely, the computation time can be reduced at the cost of increased memory use) i.e. a
situation where one thing increases and another thing decreases
As the relative costs of CPU cycles, RAM space and hard drive space change-hard drive
space has for some time been getting cheaper at a much faster rate than other components of
computers the appropriate choices for time space trade-off have changed radically.
Often, by exploiting a time space trade-off, a program can be made to run much faster.
It is a way to solve a problem in:
o Less time and by using more space/memory
o By solving a problem in very little space by spending a long amount of time.