Data Structures and Algorithms

Lecture Slides for

in C and Python
Chapter 3
Algorithms and Complexity Analysis
1

Chandan Banerjee and Atanu Das Data Structures and Algorithms in C and Python
2 Chapter Outcomes

After going through this chapter learners will be able

to think algorithmically, and get the spirit of how algorithms are designed.
to know the characteristics of algorithms.
to analyze the complexity of the algorithms.
to analyze the asymptotic performance of algorithms.
to apply complexity analysis methods on C and Python programs.
to synthesize efficient algorithms in common engineering design situations.

Data Structures and Algorithms in C and Python

Chandan Banerjee and Atanu Das
3 Content
3.1 Introduction
3.2 Complexity of Algorithms
3.3 Asymptotic Notations
3.3.1 Definition
3.3.2 Big-Oh (O) Notation
3.3.3 Big-Omega (Ω) Notation
3.3.4 Big Theta (Ө) Notation

Data Structures and Algorithms in C and Python

Chandan Banerjee and Atanu Das
4 Introduction
Algorithms are used to represent the solution to a problem by using step-by-
step statements.
These statements can be converted into programming (computer) instructions
which, ultimately form a program.

Figure: Working principle of an algorithm

Data Structures and Algorithms in C and Python

Chandan Banerjee and Atanu Das
5 Why Do We Study Algorithms?

It is very important to study algorithms from computer programming and

problem-solving perspectives. The implications of algorithms are manyfold
in computer science and software development.
“An algorithm is any well-defined computational procedure that takes
some value, or set of values, as input and produces some value or set of
values as output.”
— Thomas H. Cormen, [Link],
Proper planning is highly essential to complete a particular task in less time
and space to increase the performance of a system or application.

Definition
It is defined as a sequence of statements used to perform a task. In other
words, it is a sequence of unambiguous instructions used for solving a problem,
and can be implemented as a program on a computer.
Data Structures and Algorithms in C and Python
Chandan Banerjee and Atanu Das
6 Characteristics of Algorithm

1. Input: There should be internal or external inputs supplied to the algorithm.

2. Output: There should be at least one output obtained.

3. Definiteness: Every step of the algorithm should be clear and well-defined.

4. Finiteness: The algorithm should have a finite number of steps.

5. Correctness: Every step of the algorithm must generate the correct output.

6. Effectiveness: Execution of all operations of an algorithm requires finite

time. This measures the effectiveness of the results produced by the
algorithm.

Data Structures and Algorithms in C and Python

Chandan Banerjee and Atanu Das
7 Examples of Algorithm
Problem Statement : Write an algorithm to add two numbers and print the result.

Algo-3.1: Algorithm for adding two numbers – 1

Step 1: Initialize the values to a and b.
Step 2: Add values of a and b and store to c (c ← a + b).
Step 3: Print c.
Step 4: End.

Algo-3.2: Algorithm for adding two numbers - 2

Step 1: Initialize the values to a and b.
Step 2: Print a + b as a result.

Step 3: End.

Data Structures and Algorithms in C and Python

Chandan Banerjee and Atanu Das
8 Examples of Algorithm
Problem Statement : Find the largest number from three given numbers.

Input: A list of three numbers.

Output: The largest number from the given three numbers.

Algo-3.3: Algorithm for finding the largest number from three given numbers

Step 1: Initialize the values to a and b.

Step 2: Add values of a & b and store to c (c ← a + b).
Step 3: Print c.
Step 4: End.

Data Structures and Algorithms in C and Python

Chandan Banerjee and Atanu Das
9 How Do We Analyze Algorithms?
The theoretical study of measuring the performance of the computer program and
resource usage is the analysis of the algorithm.
A problem can be solved in more than one way. So, we can say that we may have many
algorithms to solve a particular problem.
Hence, many solution algorithms can be derived for a given problem.
The next step is to analyze those proposed solution algorithms, and identify the
best suitable algorithm for the implementation.

Data Structures and Algorithms in C and Python

Chandan Banerjee and Atanu Das
10 Algorithm vs. Pseudocode vs. Program

An algorithm is a well-defined, step-by-step procedure that allows a

computer to solve a problem systematically and logically.
Pseudocode is the simple version of the programming code. It is written in
plain English using short phrases. This is often considered as a code between
algorithms, and language-specific source code for the implementation of the
algorithm.
A program is the exact source code written for the implementation of an
algorithm using all the rules of the programming language.
In other words, program is a set of instructions written in a programming
language to implement the algorithm to solve a problem.

Data Structures and Algorithms in C and Python

Chandan Banerjee and Atanu Das
11 Differences between algorithm and program

Algorithm Program
Algorithms are written in pseudocode or Program is written in any programming
simple English statements or written in a language.
natural language.

Algorithms are independent of Program is dependent on the

programming languages. programming language.

Algorithms are produced in the design Program is produced during the

phase of software development. implementation phase of software
development.

Data Structures and Algorithms in C and Python

Chandan Banerjee and Atanu Das
12 Complexity of Algorithms
The complexity of an algorithm is concerned about how fast or slow a particular
algorithm is performing.
Performance analysis or complexity analysis of the algorithms helps us to select the
best algorithm from many algorithms to solve a particular problem.
Space Complexity: Determined by the maximum memory space required by the
algorithm.
Time Complexity: Determined by counting the number of key operations or
theoretically how much time is required to complete the task.
The complexity of an algorithm is denoted by f (n) that gives the running time and/or
the storage space required by that algorithm in terms of the input data size n.
Two points to consider for computer programming:
Appropriate data structures
Appropriate algorithm.
Data Structures and Algorithms in C and Python
Chandan Banerjee and Atanu Das
13 Space Complexity

Space complexity can be measured by the maximum memory space required

by the algorithm to complete the task.
To calculate the space complexity, we must know the memory required to
store different data types values that depend on the compiler.
For example, the C compiler (in 16 bits machine) requires the following:
2 bytes to store an integer value
4 bytes to store a floating-point value
1 byte to store a character value.
Suppose the amount of space required by an algorithm is increasing with the
increase of in-put data set, then that space complexity is called linear space
complexity.

Data Structures and Algorithms in C and Python

Chandan Banerjee and Atanu Das
14 Time Complexity
The time complexity of an algorithm is the total amount of time required by an algorithm to
complete its execution.
We can define complexity as a numerical function T(n ); i.e., time (T) requires to execute
versus the input data size (n).
We will measure time T(n ) as the number of elementary “steps” or “statements”, provided
each such step that takes constant time.
If an algorithm requires a fixed amount of time for all input data sets, then that algorithm
is said to be of constant time complexity.

The above code requires total ’n + 4' units of time to complete the tasks. Here the exact
for
time is not fixed, and it changes based on the n value inside the ‘ ’ loop.
Data Structures and Algorithms in C and Python
Chandan Banerjee and Atanu Das
15 Asymptotic Notations

The objective of analyzing the computational complexity is to classify algorithms

according to their performances. Following are three variations of time complexities:
∙ Best-case efficiency: It is the minimum number of steps that an algorithm takes
for some (specific) input data sets (of ‘n’ numbers) and is denoted by big-omega (Ω).
∙ For example, if we are sorting a set of ‘n’ numbers, and the input set is already sorted,
then we can say that it is the best-case scenario.
∙ Average-case efficiency: It may be defined as the efficiency averaged on all
possible inputs (assuming that distribution of the input is uniform) and si denoted by
the symbol big-theta (Ө).
∙ Worst case efficiency: It is the maximum number of steps that an algorithm takes
for some collection of input data sets and is denoted by the symbol big-oh (O)
∙ For example, if we are sorting a set of ‘n’ numbers, and the input set is in reverse
(opposite) order, then we can say that it is the worst-case scenario.

Data Structures and Algorithms in C and Python

Chandan Banerjee and Atanu Das
16 Asymptotic notation

Asymptotic notation is used to describe the asymptotic behavior of the

complexities of an algorithm. It is a mathematical representation of its
complexity.
Suppose, the time complexity of Algorithm 1 is ‘6n2 + 3n + 1’, and that of Algorithm
2 is ‘9n2 + 7n + 3’.
The term '3n + 1' in algorithm 1 has the least significance than the term '6n2 '. In
algorithm 2, the term '7 n + 3' has the least significance than the term '9 n2 ’.
Here, for a larger value of 'n' the value of most significant terms (6n2 and 9n2 ) is
especially larger than the value of least significant terms (3 n + 1 and 7n + 3).
So, we can ignore the least significant terms to represent the overall time
required by an algorithm when ' n' will be large.
In asymptotic notation, we use only the most significant terms to represent the
time complexity of an algorithm.
Data Structures and Algorithms in C and Python
Chandan Banerjee and Atanu Das
17 Big-Oh (O) Notation
Let, f (n) and g(n) are two positive functions of ‘n’, where ‘n’ is the input data size.
Then f (n) is big-oh (O) of g(n) if and only if there exist a positive constant C and
initial integer value n0 , such that f (n) ≤ C * g(n) for n ≥ n0 .
So, we can say f (n) = O(g(n)).

Figure: Graphical representation of big-oh (O) notation

Data Structures and Algorithms in C and Python
Chandan Banerjee and Atanu Das
18 Guiding Principles

1. The coefficients of the highest order terms should be ignored.

2. The lower order terms should be ignored.
3. A base should be changed from one constant to another constant, i.e.,
the value of the logarithm should be changed by only a constant factor.
For example,
if T1(n ) = O(f(n )) and T 2(n ) = O(g(n )) then,
(a) T1(n ) + T2(n ) = max (O(f(n )), O(g(n )))
(b) T1(n ) * T2(n ) = O(f(n ) * g(n ))
(c) O(T1(n )) = T 1(n )
(d) O(f(n ) . g(n )) = f(n ) *O(g(n ))
(e) O(f(n ) + O(f(n ))) = O( f(n ))
(f) O(f(n ))*C = O(f(n )) for any constant C
Data Structures and Algorithms in C and Python
Chandan Banerjee and Atanu Das
 Nature of Curves for Asymptotic Bounds
19 Asymptotic Bound Nature of the curve
O (1) Constant
O (log n) Logarithmic
O (n) Linear
O (n 2 ) Quadratic
O (n 3 ) Cubic
O (2 n) Exponential
O (n!) Factorial

Analyzing Growth of Functions

n g(n)
log2 n n n log2 n n2 n3 2n
1 0 1 1 1 1 2
2 1 2 2 4 8 4
4 2 4 8 16 64 16
8 3 8 24 64 512 256
16 4 16 64 256 4096 65536

Relation among the complexity of the algorithms in terms of big-oh is given below:

O (1) < O (log n) < O( n) < O (n * log n) < O (n2 ) < O (n3 ) < O (2 n).
Data Structures and Algorithms in C and Python
Chandan Banerjee and Atanu Das
20 Analyzing Growth of Functions
Relation among the complexity of the algorithms in terms of big-oh is given below:

O (1) < O (log n) < O( n) < O (n*log n) < O (n2 ) < O (n3 ) < O (2 n).

Data Structures and Algorithms in C and Python

Chandan Banerjee and Atanu Das
21 Some Examples
Example: Quadratic function: f ( n) = 6n2 + 4n.
Given that f (n) = 6n2 + 4 n;
So, f ( n) ≤ 7 n2 since 4 n ≤ n2 implies n ≥ 4;
Hence, C = 7, n0 = 4 and g( n) = n2;
So, f(n) = O( n2), [Since f( n) ≤ C * g( n) and n ≥ n0 to represent as f( n) = O( g( n)) by definition].

Example: Cubic function: f ( n) = 4n3 + n2 + 4n.

Given that f ( n) = 4n3 + n2 + 4 n
≤ 4n3 + 2n2, for n2 ≥ 4n and n ≥ 4;
≤ 4n3 + n3 , for n3 ≥ 2n2 and n ≥ 2;
≤ 5n 3
Hence, C = 5, n0 = 4 and g( n) = n3.
So, f ( n) = O( n3), [Since f ( n) ≤ C * g( n) and n ≥ n0 to represent as f( n) = O(g(n)) by definition].

Data Structures and Algorithms in C and Python

Chandan Banerjee and Atanu Das
22 Some Examples
Example: Prove that n2 + 2n + 1 = O( n2).
We must first find C and n0 such that n2 + 2 n + 1 ≤ C * n2, for all n ≥ n0.
If n0 = 1, then 1 ≤ n < n2 for all n ≥ 1.
So, n2 + 2 n + 1 ≤ n2 + 2 n2 + n2 = 4n2.
It follows that C = 4 and f( n) = O( n2).

Example: Exponential function: f( n) = 2n + 6n2 + 3n.

f( n) = 2n + 6 n2 + 3 n
≤ 2n + 6 n2 + n2 for n2 ≥ 3n
≤ 2n + 7 n2 for 2 n ≥ n2 where n ≥ 4
≤ 2n + 7 * 2n, since n2 ≤ 2n
≤ 8 * 2n
Hence, C = 8, n0 = 4,
So, f ( n) = O(2n).

Data Structures and Algorithms in C and Python

Chandan Banerjee and Atanu Das
23 Measuring the Complexity of C Programs

Answer: O(n2 )

• Time required by each operation/statement to execute is considered as 1-unit time. In the above code,
there is nested loop i and j, and each loop will be executed n times each. So, the total for
loop will take n * n
= n2 unit time.
• If we increase the value of ‘n’ then the time required also increases quadratically. We should calculate time
complexity considering ‘n’ is a large value. If ‘n’ is large then in constant ’3’ unit-time in the C program will be
negligible; then we can say that the complexity of the code is O(n2).

Data Structures and Algorithms in C and Python

Chandan Banerjee and Atanu Das
24 Measuring the Complexity of Python Programs

Answer: O(n2 )

• Time required by each operation/statement to execute is considered as 1-unit time. In the above code,
there is nested loop i and j, and each loop will be executed n times each. So, the total for loop will take n * n
= n2 unit time.
• If we increase the value of ‘n’ then the time required also increases quadratically. We should calculate time
complexity considering ‘n’ is a large value. If ‘n’ is large then in constant ‘1’ unit-time in the Python program
will be negligible, then we can say that the complexity of the code is O(n2).

Data Structures and Algorithms in C and Python

Chandan Banerjee and Atanu Das
25 Big-Omega (Ω) Notation

f (n) and g(n) are two positive functions of ‘n’, where ‘n’ is the input data size.
Then f (n) is big-omega (Ω) of g(n), if and only if there exists a positive
constant C, and initial integer value n0 , such that f (n) ≥ C * g(n) and n ≥ n0 .
So, we can say f (n) = Ω (g(n)).

Figure: Graphical representation of big-omega ( Ω) notation

Data Structures and Algorithms in C and Python
Chandan Banerjee and Atanu Das
26 Big-Omega (Ω) Notation (Example)

Suppose f (n) and g(n) are two functions. f (n) = 3 n + 2 and g(n) = n.

If we try to represent f (n) as Ω(g(n)) then f (n) ≥ C * g(n) for all values of
C > 0 and n0 ≥ 1.

f (n) ≥ C * g(n) must be true.

⇒ f (n) = 3 n + 2 ≥ C * n, for all values of C = 1 and n ≥ 1.

By using big-omega notation, we can write 3 n + 2 = Ω(n).

Data Structures and Algorithms in C and Python

Chandan Banerjee and Atanu Das
27 Big Theta (Ө) Notation
f (n) and g(n) are two positive functions of ‘n’, where ‘n’ is the input data
size.
Then f (n) is big theta (Ө) of g(n), if and only if there exists two positive
constants C1 and C2 , such that C1 * g(n) ≤ f (n) ≤ C2 * g(n) for all n ≥ n0 , C1 > 0,
C2 > 0 and n0 ≥ 1.
So, we can say that f (n) = Ө(g(n)).

Figure: Graphical representation of big-theta (Ө) notation

Data Structures and Algorithms in C and Python
Chandan Banerjee and Atanu Das
28 Big-Omega (Ω) Notation (Example)

Suppose, f (n) and g(n) are two functions where f (n) = 3 n + 2 and g(n) = n.

If we try to represent f (n) as Θ( g(n)), then it must satisfy

C1 g(n) ≤ f (n) ≤ C2 g(n) for all values of C1 > 0, C2 > 0 and n0 ≥ 1.

C1 g(n) ≤ f (n) ≤ C2 g(n) ⇒ C1 n ≤ 3n + 2 ≤ C2 n. for C 1 = 1, C2 = 4 and n ≥ 2.

By using big-omega notation, we can write 3 n + 2 = Ω(n).

Data Structures and Algorithms in C and Python

Chandan Banerjee and Atanu Das
29 Comparison among asymptotic notations

Ω(g) grows at least as fast as g, i.e., Ө( g) grows at the same rate as g and O(g) grows slower
than g. So, Ө( g) function lies in the intersection area of Ω(g) and O(g) as Ө( g) indicates
expected average running time of algorithms on ‘n’ inputs, or Ө( g) belongs to the
intermediate zone of best-case and worst-case running times.

Data Structures and Algorithms in C and Python

Chandan Banerjee and Atanu Das
30

END

Data Structures and Algorithms in C and Python

Chandan Banerjee and Atanu Das