Page 25 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes
Did u know? It is preferred to choose an efficient algorithm, so it would be nice to have
metrics for comparing algorithm efficiency.
The complexity of an algorithm is a function describing the efficiency of the algorithm in terms
of the amount of data the algorithm must process. Usually there are natural units for the domain
and range of this function. There are two main complexity measures of the efficiency of an
algorithm:
Time complexity is a function describing the amount of time an algorithm takes in terms
of the amount of input to the algorithm. “Time” can mean the number of memory accesses
performed, the number of comparisons between integers, the number of times some
inner loop is executed, or some other natural unit related to the amount of real time the
algorithm will take. We try to keep this idea of time separate from “wall clock” time, since
many factors unrelated to the algorithm itself can affect the real time (like the language
used, type of computing hardware, proficiency of the programmer, optimization in the
compiler, etc.). It turns out that, if we chose the units wisely, all of the other stuff doesn’t
matter and we can get an independent measure of the efficiency of 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. The better the time complexity of
an algorithm is, the faster the algorithm will carry out his work in practice. Apart from
time complexity, its space complexity is also important: This is essentially the number of
memory cells which an algorithm needs. A good algorithm keeps this number as small as
possible, too.
We often speak of “extra” memory needed, not counting the memory needed to store the
input itself. Again, we use natural (but fixed-length) units to measure this. We can use
bytes, but it’s easier to use, say, number of integers used, number of fixed-sized structures,
etc. In the end, the function we come up with will be independent of the actual number of
bytes needed to represent the unit. Space complexity is sometimes ignored because the
space used is minimal and/or obvious, but sometimes it becomes as important an issue as
time.
There is often a time-space-tradeoff involved in a problem, that is, it cannot be solved with few
computing time and low memory consumption. One then has to make a compromise and to
exchange computing time for memory consumption or vice versa, depending on which algorithm
one chooses and how one parameterizes it.

Example: We might say “this algorithm takes n time,” where n is the number of items
2
in the input. Or we might say “this algorithm takes constant extra space,” because the amount of
extra memory needed doesn’t vary with the number of items processed.

The difference between space complexity and time complexity is that space can be reused. Space
complexity is not affected by determinism or nondeterminism. Amount of computer memory
required during the program execution, as a function of the input size.
A small amount of space, deterministic machines can simulate non-deterministic machines,
where as in time complexity, time increase exponentially in this case. A non-deterministic TM
using O(n) space can be changed to a deterministic TM using only O 2(n) space.

Task Analyze the difference between time and space complexity.

18 LOVELY PROFESSIONAL UNIVERSITY