Page 38 - DCAP407_DATA_STRUCTURE

Unit 2: Complexity Analysis

Quicksort has an average case time complexity of n * log(n).

In general, time complexity helps to estimate the number of functions required to solve a problem of
size n.
Space Complexity
Space complexity is the amount of memory an algorithm requires to run. The space complexity of an
algorithm can be determined by relating the size of a problem (n) to the amount of memory (s) needed
to solve that problem. Thus, the space complexity can be computed by using the below two
components:
1. Fixed Space Requirement: It is the amount of space acquired by fixed sized structure, variables,
and constants.
2. Variable Space Requirement: It is the amount of space required by the structured variables, whose
size depends on particular problem instance.

Therefore, to calculate the space complexity of an algorithm we have to consider the following two
factors:
1. Constant characteristics
2. Instant characteristics
Thus, the space requirement S(p) is given as:

S(p) = C + Sp
Here, C is the constant (required fixed space) and Sp is the space that depends on a particular instance
of variables.
Let us take an example to determine the space complexity of the variables used in a program.

Algorithm: To compute the sum of three elements
//Input: x, y, and z are of integer type
Input x, y, z
//Output: The sum of three integers is returned
return x+y+z
Thus, if each of the input elements occupies 2 bytes of memory space,
then the inputs x, y, z will require a total memory size of 6 bytes.
In general, space complexity helps to define the amount of memory required to solve a particular
problem.

Write a searching algorithm and find out the best, worst, and average case time
complexity of that algorithm.

Time Space Tradeoff

Most of the algorithms are constructed to work with inputs of arbitrary length. Usually, the efficiency of
an algorithm is stated as a function relating to time complexity or space complexity.
Time space tradeoff in context with algorithms relates to the execution of an algorithm. The execution of
an algorithm can be done in a short time by using more memory, because execution time increases with
less memory. Therefore, proper selection of one alternative over the other is the tradeoff.
Problems like sorting or matrix-multiplication have many choices of algorithms. Some of the choices are
extremely space-efficient and some are extremely time-efficient. Research in time-space tradeoff lower

LOVELY PROFESSIONAL UNIVERSITY 31