Data Structures and Algorithms (Important notes by K Munivra Prasad)

LECTURE NOTES

on
DATA STRUCTURES
201 8 – 201 9

I B. Tech II Sem e s t e r (R 17 )
Mr. K Munivara Prasad, Associ at e Profe s s o r




CHADALAWADA RAMANAMMA ENGINEERING COLLEGE
(AUTONOMOUS)
Chadalawada Nagar, Renigunta Road, Tirupati – 517 506

Department of Computer Science and Engineering




1

, UNIT-I

PROGRAMMING PERFORMANCE

Perfor m a n c e of a progra m: The performance of a program is
measured based on the amount of computer memory and time needed
to run a program.

The two approache s which are used to measur e the performa nc e of the
progra m are:

1. Analytical m et h o d à called the Performance Analysis.
2. Experi m e n t a l m eth o d à called the Performance Measurem e n t .

SPACE COMPLEXITY

Space com p l exi t y: The Space complexity of a program is defined as
the amount of memory it needs to run to completion.

As said above the space complexity is one of the factor which
accounts for the performa nc e of the progra m. The space complexity can
be measur e d using experime n t al method, which is done by running the
progra m and then measuring the actual space occupied by the progra m
during execution. But this is done very rarely. We estimate the space
complexity of the program before running the progra m.

Spac e compl exity is the sum of the followin g comp o n e n t s :

(i) Instruc t i o n space:

The progra m which is written by the user is the source progra m.
When this progra m is compiled, a compiled version of the progra m is
generat e d. For executing the progra m an executa ble version of the
progra m is generat e d. The space occupied by these three when the
progra m is under execution, will account for the instruction space.


(ii) Data space:

The space needed by the constants, simple variables, arrays,
structur es and other data structure s will account for the data space.

The Data space depends on the following factors:

• Structure size – It is the sum of the size of compone n t
variables of the structur e .
• Array size – Total size of the array is the product of the size
of the data type and the numbe r of array locations.




2

,(iii) Environ m e n t stack space:

The Environm en t stack space is used for saving information needed
to resume execution of partially completed functions. That is whenever
the control of the program is transferre d from one function to another
during a function call, then the values of the local variable of that
function and return address are stored in the environme n t stack. This
information is retrieved when the control comes back to the same
function.

The environment stack space depends on the following factors:

• Return address
• Values of all local variables and formal param e t e r s .

The Total space occupied by the progra m during the execution of the
progra m is the sum of the fixed space and the variable space.

(i) Fixed spac e - The space occupied by the instruction space,
simple variables and constants.

(ii) Variable spac e – The dynamically allocated space to the
various data structur e s and the environme n t stack space varies
according to the input from the user.
S pace com p l exi t y S( P) = c + S p

c à Fixed space or constant space
S p à Variable space

We will be interest e d in estimating only the variable space because that
is the one which varies according to the user input.
TIME COMPLEXITY

Time com p l exi t y: Time complexity of the program is defined as the
amount of computer time it needs to run to completion.

The time complexity can be measure d, by m easuring the time
taken by the progra m when it is executed. This is an experiment al
method. But this is done very rarely. We always try to estimate the time
consum e d by the progra m even before it is run for the first time.

The time complexity of the program depends on the following
factors:

• Compiler used – some compilers produce optimized code
which consum es less time to get executed.
• Compiler options – The optimization options can be set in the
options of the compiler.
• Target computer – The speed of the compute r or the number
of instructions executed per second differs from one
computer to another.


3

, The total time taken for the execution of the progra m is the sum of the
compilation time and the execution time.

(i) Compil e time – The time taken for the compilation of the
progra m to produce the interme diat e object code or the
compiler version of the progra m. The compilation time is taken
only once as it is enough if the progra m is compiled once. If
optimized code is to be genera t e d, then the compilation time
will be higher.

(ii) Run time or Executi o n time - The time taken for the
execution of the progra m. The optimized code will take less
time to get executed.

Time com p l exi t y T(P) = c + T p

c à Compile time
Tp à Run time or execution time

We will be intereste d in estimating only the execution time as this is the
one which varies according to the user input.

Estima t i n g the Executi o n time:

Progra m step: Program step is a meaningful segment of a program
which is independent of instance characteristics. Instance
characteristics are the variables whose values are decided by the user
input at that instant of time.

Steps in estimating the execution time of program:

(i) Identify one or more key operations and determine the number of
times these are perform ed. That is find out how many key
operations are present inside a loop and how many times that loop
is executed.
(ii) Determine the total number of steps executed by the progra m.

The time complexity will be proportional to the sum of the above two.

ASYMPTOTIC NOTATIONS

Asymptotic notations – Asymptotic notations are the notations used to
describe the behavior of the time or space complexity.

Let us represe n t the time complexity and the space complexity using the
common function f(n).

The various asymptotic notations are:

(i) O ( Big Oh notation )


4