Department of CSE (AI & ML), KITSW U18AI604 Design and Analysis of Algorithms

6CSE AY:2024-25
CDT2 - LECTURE SUMMARY
Space complexity and Time complexity
CDT2
Topics Covered
(As course faculty, how do you motivate your course students to learn these
Motivation
topics?
(Why you
(students) should Students will learn the effective problem solving in computing, and calculate
learn these topics? )
time and space complexity
Lecture Learning Outcomes (LLOs): After completion of this lecture, you should be able to…
LLO1
On topic 1
understand the time complexity
Lecture level Practice Problems:
LLO1: Time complexity
Compute Time Complexity for Printing out a matrix
Compute Time Complexity for Matrix multiplication

LLO2
On topic 2
Understand space complexity.
LLO2: Space Complexity
Compute Space Complexity for Matrix multiplication

CDT2 – Lecture Summary – Key Takeaways

Space Complexity:

The Space Complexity of any algorithm P is given by S(P)=C+SP(I),C is constant.

1. Fixed Space Requirements (C)

Independent of the characteristics of the inputs and outputs
– It includes instruction space
– space for simple variables, fixed-size structured variable, constants
2. Variable Space Requirements
(SP(I)) depend on the instance
characteristic I
– number, size, values of inputs and outputs associated with I
– recursive stack space, formal parameters, local variables, return address
Examples:
*Program 1 :Simple arithmetic function
Algorithmabc( a, b, c)
{
return a + b + b * c + (a + b - c) / (a + b) + 4.00;
}

SP(I)=0

HenceS(P)=Constant

Program 2: Iterative function for sum a list of numbers

Prepared by: Dr. M. SUJATHA, Dept. of CSE (AI & ML), KITSW Page 1 of 5
Department of CSE (AI & ML), KITSW U18AI604 Design and Analysis of Algorithms
6CSE AY:2024-25
CDT2 - LECTURE SUMMARY
Algorithm sum( list[ ], n)
{

tempsum =
0; for i
= 0 ton
do
tempsum += list
[i]; return
tempsum;
In the above example list[] is dependent on n. Hence S P(I)=n. The remaining variables are i,n,
tempsum each requires one location.

Hence S(P)=3+n

*Program 3: Recursive function for sum a list of numbers

Algorithmrsum( list[ ], n)
{

If (n<=0) then

return

0.0

else
return rsum(list, n-1) + list[n];

In the above example the recursion stack space includes space for formal parameters local
variables and return address. Each call to rsum requires 3 locations i.e for list[],n and
return address .As the length of recursion is n+1.

S(P)>=3(n+1)

Time complexity:

T(P)=C+TP(I)

It is combination of-Compile time (C)

independent of instance
characteristics
-run (execution) time TP
dependent of instance characteristics
Time complexity is calculated in terms of program step as it is difficult to know the
complexities of individual operations.
Definition: Aprogram step is a syntactically or semantically meaningful program
segment whose execution time is independent of the instance characteristics.

Program steps are considered for different statements as : for comment zero steps .
assignment statement is considered as one step. Iterative statements such as “for,
while
and until-repeat” statements, we consider the step counts based on the expression .
Prepared by: Dr. M. SUJATHA, Dept. of CSE (AI & ML), KITSW Page 2 of 5
Department of CSE (AI & ML), KITSW U18AI604 Design and Analysis of Algorithms
6CSE AY:2024-25
CDT2 - LECTURE SUMMARY

Methods to compute the step count:

1) Introduce variable count into programs
2) Tabular method
– Determine the total number of steps contributed by each
statement step per execution frequency
– add up the contribution of all statements

program 1.with count statements

Algorithm sum( list[ ], n)

{
tempsum := 0; count++; /* for assignment
*/ for i := 1 to n do {
count++; /*for the for loop */
tempsum := tempsum + list[i]; count++; /* for assignment */
}
count++; /* last execution
of for */ return tempsum;
count++; /* for

return */ Hence

T(n)=2n+3 Program

:Recursive sum

Algorithmrsum( list[ ], n)
{
count++; /*for if
conditional */ if (n<=0) {
count++; /* for return */ return
0.0 }

else

returnrsum(list, n-1) + list[n];

count++;/*for return and rsum invocation*/

T(n)=2n+2

Program for matrix addition

Algorithm add( a[ ][MAX_SIZE], b[ ][MAX_SIZE],c[ ][MAX_SIZE], rows, cols )

{
for i := 1 to rows do {
count++; /* for i for
loop */ for j := 1
to cols do {
Prepared by: Dr. M. SUJATHA, Dept. of CSE (AI & ML), KITSW Page 3 of 5
Department of CSE (AI & ML), KITSW U18AI604 Design and Analysis of Algorithms
6CSE AY:2024-25
CDT2 - LECTURE SUMMARY
count++; /* for j for
loop */ c[i][j] :=
a[i][j] + b[i][j];
count++; /* for assignment statement */
}
count++; /* last time of j for loop */
}
count++; /* last time of i for loop */
}

T(n)=2rows*cols+2*rows+1

II

Tabular method.

Complexity is determined by using a table which includes steps per execution(s/e) i.e
amount by which count changes as a result of execution of the statement.

Frequency – number of times a statement is executed.

Statement s/e Frequency Total steps

Algorithm sum( list[ ], n) 0 - 0
{ 0 -1 0
tempsum := 0; for i 1 n+1 n 1
:= 0 ton do 1 1 n+1 n
tempsum := tempsum + list [i]; return 1 0 1
tempsum; 1 0
} 0

Total 2n+3

Statement s/e Frequency Total steps

n=0 n>0 n=0 n>0
Algorithmrsum( list[ ], n) 0 - - 0 0
{ 0 - - 0 0
If (n<=0) then 1 1 1 1 1
return 0.0; 1 1 0 1 0
else 0 0 0 0 0
return rsum(list, n-1) + list[n]; 1+x 0 0 1 0 1+x 0
0 0 0
}

Total 2 2+x

Prepared by: Dr. M. SUJATHA, Dept. of CSE (AI & ML), KITSW Page 4 of 5
Department of CSE (AI & ML), KITSW U18AI604 Design and Analysis of Algorithms
6CSE AY:2024-25
CDT2 - LECTURE SUMMARY

Statement s/e Frequency Total steps

Algorithm add(a,b,c,m,n) 0 - 0
{ 0 - 0
for i:=1 to m do 1 m+1 m+1
for j:=1 to n do 1 m(n+1) mn+m
c[i,j]:=a[i,j]+b[i,j]; 1 mn mn
} 0 - 0

Total 2mn+2m+1

Complexity of Algorithms

The complexity of an algorithm M is the function f(n) which gives the running time and/or
storage space requirement of the algorithm in terms of the size ‘n’ of the input data.
Mostly, the storage space required by an algorithm is simply a multiple of the data size
‘n’. Complexity shall refer to the running time of the algorithm.
The function f(n), gives the running time of an algorithm, depends not only on the size ‘n’ of
the input data but also on the particular data. The complexity function f(n) for certain
cases are:

1. Best Case : The minimum possible value of f(n) is called the best case.

2. Average Case : The average value off(n).

3. Worst Case : The maximum value of f(n) for any key possible input.

The field of computer science, which studies efficiency of algorithms, is known as analysis of
algorithms.
Algorithms can be evaluated by a variety of criteria. Most often we shall be interested in the
rate of growth of the time or space required to solve larger and larger instances of a
problem. We will associate with the problem an integer, called the size of the problem,
which is a measure of the quantity of input data. Rate of Growth:

The following notations are commonly use notations in performance analysis and used to
characterize the complexity of an algorithm:

CDT2 - LECTURE LEVEL PRACTICE PROBLEMS (LLPs) to test the LLOs

To test whether you achieved the learning outcomes of this lecture, you should be able to solve the following
LLPs, in the class itself, after completion of the lecture. Minimum one question / problem (LLP) is designed to
test each expected LLO.
1 LLP1(on LLO1): calculate the time complexity of factorial of given number
2 LLP2 (on LLO2): Calculate of time complexity of sum of n natural number
3 LLP3 (on LLO3): find the time complexity of recursion sum of n number

Prepared by: Dr. M. SUJATHA, Dept. of CSE (AI & ML), KITSW Page 5 of 5