Page 39 - DCAP407_DATA_STRUCTURE

Data Structure

bounds seeks to prove that for certain problems, no algorithms exist that achieve lesser time complexity
and space complexity simultaneously.
Let us take an example to understand time space tradeoff more clearly.

Assume that you are given a file of records which contains names, social
security numbers, and other additional information among its fields. You
can easily sort the file alphabetically and run a binary search to find the
record for a given name. Suppose you are given only the social security
number of a person and you are required to find the record for a given
name. Then to solve such a problem, you can create a file which will be
sorted numerically according to the social security number. But, this
process increases the space required for sorting the data.
Another way is to have the main file sorted numerically by social security
number and to have an auxiliary array with only two columns as shown
in figure 2.7. The first column contains an alphabetized list of the names
and the second column contains pointers which give the locations of the
corresponding records in the main file. This method is used frequently,
since the required additional space is minimal when compared to the
amount of extra information it provides.
Figure 2.7 shows Time-Space tradeoff.

Figure 2.7: Time Space Tradeoff

Source: Lipschutz, S. (2011). Data Structures with C. Delhi: Tata McGraw-Hill.
2.3 Algorithmic Analysis

Analysis of an algorithm is required to determine the amount of resources such as time and storage
necessary to execute the algorithm. Usually, the efficiency or running time of an algorithm is stated as a
function which relates the input length to the time complexity or space complexity.

Algorithm analysis framework involves finding out the time taken and the memory space required by a
program to execute the program. It also determines how the input size of a program influences the
running time of the program.

In theoretical analysis of algorithms, it is common to estimate their complexity in the asymptotic sense,
i.e., to estimate the complexity function for arbitrarily large input. Big-O notation, Omega notation, and
Theta notation are used to estimate the complexity function for large arbitrary input.

32 LOVELY PROFESSIONAL UNIVERSITY