Time and Space
Complexity Analysis
of Algorithm
What is an Algorithm?
In computer science, whenever we want to solve some
computational problem then we define a set of steps that need
to be followed to solve that problem. These steps are
collectively known as an algorithm.
For example, you have two integers "a" and "b" and you want
to find the sum of those two number. How will you solve
this? One possible solution for the above problem can be:
Take two integers as input
create a variable "sum" to store the sum of two integers
put the sum of those two variables in the "sum" variable
return the "sum" variable
What do you mean by a good Algorithm?
There can be many algorithms for a particular problem. So, how
will you classify an algorithm to be good and others to be bad?
Let's understand the properties of a good algorithm:
Correctness: An algorithm is said to be correct if for every set of input it
halts with the correct output. If you are not getting the correct output for
any particular set of input, then your algorithm is wrong.
Finiteness: Generally, people ignore this but it is one of the important
factors in algorithm evaluation. The algorithm must always terminate
after a finite number of steps. For example, in the case of recursion and
loop, your algorithm should terminate otherwise you will end up having
a stack overflow and infinite loop scenario respectively.
Efficiency: An efficient algorithm is always used. By the term efficiency,
we mean to say that:
What do you mean by a good Algorithm?
The algorithm should efficiently use the resources available to the
system.
The computational time (the time taken to generate an output
corresponding to a particular input) should be as less as possible.
The memory used by the algorithm should also be as less as
possible. Generally, there is a trade-off between computational
time and memory. So, we need to find if the time is more
important than space or vice-versa and then write the algorithm
accordingly.
So, we have seen the three factors that can be used to evaluate an
algorithm. Out of these three factors, the most important one is
the efficiency of algorithms. So let's dive deeper into the
efficiency of the algorithm.
Algorithm Efficiency
The efficiency of an algorithm is mainly defined by
two factors i.e. space and time.
A good algorithm is one that is taking less time
and less space, but this is not possible all the time.
There is a trade-off between time and space. If you
want to reduce the time, then space might
increase.
Similarly,if you want to reduce the space, then the
time may increase. So, you have to compromise
with either space or time. Let's learn more about
space and time complexity of algorithms.
Space Complexity and Time Complexity
Space Complexity
Space Complexity of an algorithm denotes the total space used or
needed by the algorithm for its working, for various input sizes.
Time Complexity
The time complexity is the number of operations an algorithm performs to
complete its task with respect to input size (considering that each
operation takes the same amount of time). The algorithm that performs
the task in the smallest number of operations is considered the most
efficient one.
Input Size: Input size is defined as total number of elements present in the
input. For a given problem we characterize the input size n approproately.
For example:
Sorting problem: Total number of item to be sorted
Graph Problem: Total number of vertices and edges
Numerical Problem: Total number of bits needed to represent a number
Space Complexity and Time Complexity
The time taken by an algorithm also depends on the
computing speed of the system that you are using, but we
ignore those external factors and we are only concerned on
the number of times a particular statement is being executed
with respect to the input size.
Let's say, for executing one statement, the time taken is 1sec,
then what is the time taken for executing n statements, It will
take n seconds.
One thing that is to be noted here is that we are finding the
time taken by different algorithms for the same input because
if we change the input then the efficient algorithm might take
more time as compared to the less efficient one because the
input size is different for both algorithms.
