Page 36 - DCAP407_DATA_STRUCTURE

Unit 2: Complexity Analysis

hour periods. If the time is 6:00 now, then 9 hours later it will be 3:00. Usual addition suggests that the
later time must be 6 + 9 = 15, but this is not true because clock time "wraps around" every 12 hours;
there is no "15 o'clock". Likewise, if the clock starts at 12:00 noon then after 20 hours the time will be 8:00
the next day, rather than 32:00. The hour number starts all over again after it reaches 12. Therefore, this
is arithmetic modulo 12.

Two numbers x and y are said to be equal or congruent module N if their
difference is exactly divisible by n i.e. n/(x-y).
Generally, x and y are non-negative and N is a positive integer. Thus, we can
write
x=y (mod n)
If the difference between x and y is an integer multiple of n, then the number
n is called the modulus of congruence.
2.2 Algorithmic Complexity and Time Space Tradeoff

Complexity is a measure of performance of an algorithm. The complexity of computation is a
characterization of time and space requirements, which helps to solve a problem using a specific
algorithm. Computational complexity is mostly concerned with the lower bound.
2.2.1 Algorithmic Complexity

We can determine the efficiency of an algorithm by calculating its performance. Following are the two
factors that help us to determine the efficiency of an algorithm:
1. Total time required by an algorithm to execute.

2. Total space required by an algorithm to execute.
Thus, the two main considerations required to analyze the program are:

1. Time complexity
2. Space complexity
The amount of computer time required to solve a problem is the time complexity of an algorithm and
the amount of memory required to compute the problem is the space complexity of an algorithm.

Time Complexity
Time complexity of an algorithm is the amount of time required by an algorithm to execute. It is always
measured using the frequency count of all important statements or the basic instructions. This is
because the clock limitation and multiprogramming environment makes it difficult to obtain a reliable
timing figure.
The time taken by an algorithm is the sum of compile time and run time. The compile time does not
depend on the instance characteristics, as a program once compiled can be run many times without
recompiling. Thus, only the run-time of the program matters while calculating time complexity. Let us
take an example to get a clear idea of how time complexity of an algorithm is computed.

LOVELY PROFESSIONAL UNIVERSITY 29