Data Structures and Algorithm, Dept.

of CSE, SRM AP

o Algorithm
o Complexities
What is an algorithm
 Brassard and Brately coined the term algorithmics, which
they defined as “the systematic study of the fundamental
techniques used to design and analyze the efficient
algorithms”.

Approaches to represent an algorithm

Verbal Visual
o Flow Chart
o Pseudo Code o FSM Diagram
o UML Diagram

CHANDRA [Link] AP19110010028

Pseudo Code
 Pseudocode is an English like representation of the
algorithm logic.
 It is part English, part Structured Code.
 The English part provides a relaxed syntax that
describes What must me done without showing
unnecessary details , such as error messages.
 The code part consists of an extended version of the
basic algorithm constructs such as:
 Sequence
 Selection
 Iteration
 Pseudocode is independent of any programming
language and is used to describe an algorithm.
CHANDRA [Link] AP19110010028
Example of a pseudocode

 This data definition

describes a node in a self- set count to 0
referential list that consists node
of: data
 a nested structured link
(data) end node
 a pointer to the next node
(link).
Algorithm to add two numbers:
1. Read A, B.
2. Set SUM: = A+B.
3. Write SUM.
4. Exit.

CHANDRA [Link] AP19110010028

Flowchart

 An algorithm can be represented using pictorial

representation as a flow chart
 Example

CHANDRA [Link] AP19110010028

Components of an Algorithm

 Algorithm Header – that names it, lists its

parameters and describes any preconditions
(inputs) and post conditions (output).
 Purpose – a short statement about what the
algorithm does – generic statements, not details.
 Condition:
 Pre Condition(s) – lists any precursor
requirements for the parameters. Sometimes
there might be no parameters also.
 Post Condition – identifies any action taken and
the status of any output parameter.
 Return: If a value is written by the algorithm,
then it is identified by a RETURN condition.
 Statement Constructs

CHANDRA [Link] AP19110010028

Components of an Algorithm
Algorithm Header – that names it, lists its parameters and
describes any preconditions (inputs) and post conditions
(output).
Purpose – a short statement about what the algorithm does
– generic statements, not details.

Condition:
Pre Condition(s) – lists any precursor requirements for
the parameters. Sometimes there might be no
parameters also.
Post Condition – identifies any action taken and the
status of any output parameter.
Return: If a value is written by the algorithm, then it is
identified by a RETURN condition.
Statement Constructs
CHANDRA [Link] AP19110010028
Structure of an Algorithm

1. Input Step
2. Assignment Step
3. Decision Step
4. Repetitive
5. Output Step

Explanation with an Example

Input Step : Consider two operands for addition

Assignment Step: Set the pair of digits from the two

numbers and the previous carry digit if it exits, for
addition
CHANDRA [Link] AP19110010028
Structure of an Algorithm

Decision Step : Decision at each step whether the

added digits yield a value that is greater than 10 if so, to
generate the appropriate carry digit

Repetitive Step : Repeats the process for every paior of

digits beginning from the least significant digit onwards.

Output Step: Releases the outputs – Here is the Sum of

two numbers

CHANDRA [Link] AP19110010028

Properties of Algorithm

 Finiteness : An algorithm must terminate after a finite

number of steps
 Definiteness : The steps of the Algorithm must be
precisely defined or Specified
 Generality :An algorithm must be generic enough to solve
all the problems of a particular class
 Effectiveness : The operation of the algorithm must be
basic enough to be put down on pencil and [Link]
should not be too complex to warrant writing another
algorithm for the operation
 Input – Output : The algorithm must have certain initial
and precise inputs, and outputs that may be generated
both ad tis intermediate and final steps
CHANDRA [Link] AP19110010028
Algorithms

 When there is a problem to be solved it is probable that

several algorithms crop up for its solution and therefore
one is at a loss to know which one is the best.
 Then how to decide which algorithm is best for a given
situation or scenario?
 The one which performs better, i.e., the one which is more
efficient.
 How do we know which is more efficient?
 i.e., How to measure efficiency of an algorithm or
algorithms?
Algorithms

 Usually it is done in the scale of TIME and SPACE

complexities.
 In time measurement we would be looking for the
fastest algorithm or which performs its-task in
minimum possible time – termed as Time Complexity.
 In space measurement it would mean looking for an
algorithm that consumes or needs limited memory
space for its execution – termed as Space Complexity.

In general, and in reality, time complexity is stressed upon than

space complexity except for scenarios where there is limited
memory – such as in WSN and IoT networks.
Time Complexity

 The time complexity of an algorithm can be computed

either by an
 Empirical approach
 Theoretical approach
Time Complexity

 The time complexity of an algorithm can be computed

either by an
 Empirical approach
 Theoretical approach
 Empirical or Posteriori Testing: This approach calls for
implementing the algorithms, in the form of a program
code, and executing them on a computer.
 The developed/proposed algorithms are tested for
various instances of the inputs.
 The algorithm whose implementation yields the least
time, is considered as the best among the set of
algorithms.
Time Complexity

 Theoretical or apriori Testing: This method calls for

mathematically determining the resources as time and
space needed by the algorithm, as a function of a
parameter related to the instances of the problem
considered.
 A parameter that is often used is the size of the input
instances.
Time Complexity

 Theoretical or apriori Testing: This method calls for

mathematically determining the resources as time and
space needed by the algorithm, as a function of a
parameter related to the instances of the problem
considered.
 A parameter that is often used is the size of the input
instances.
Time Complexity

 Let is consider a program statement, for example,

x = x+2
in a sequential programming environment.
 Apriori estimation involves:
 The number of times the statement is executed in a
program, known as the frequency count of the
statement.
 The time taken for a single execution of the
statement – this is machine dependent.
 In general, apriori analysis considers only the first
factor and computes the efficiency of the program as
a function of the total frequency count of the
statements on a program.
Time Complexity
 Let us now estimate the total frequency count of the
statement x = x+2 occurring in the following three
program statements: …
… for j=1 to n do
…
for k=1 to n do for k=1 to n do
x = x+2
x=x+2; x = x+2
…
end end
… end
…

1
n n2
 Program Statement Frequency Count
…
x=x+2 1
…

…
for k = 1 to n do (n+1)
x = x + 2; n
end n
… ----------------------------------------
Total: (n+1) + n + n = 3n+1 = n
…
for j = 1 to n do

for k = 1 to n do

x=x+2

end

end
…
Tips on mathematical formulae.


Asymptotic Notations

 Apriori analysis requires mathematical notations to

express the time complexity of algorithms.
 Technically, these notation are termed asymptotic
notations since they are meaningful approximation of
function.
Asymptotic Notations

 Definition-1:
 f(x) = O(g(n)) – read as “f of n is big oh of g of n.
 If there exists a positive integer n0 and a positive
number C such that |f(n)| ≤ c |g(n)|, for all n ≥ no ;
and for C > 0 and no ≥ 1
 E.g.,

f(n) g(n) Complexity

16n3 + 77n2 + 12n n3 f(n) = O(n3)
34n – 90 n f(n) = O(n)
56 1 f(n) = O(1)
More on O(n)
 f(n) ≤ cg(n)
 Let f(n) = 3n+2 and g(n) = c*n
 The as per the definition we have |f(n)| ≤ c |g(n)|
 Now find the value of c that satisfies the above
mentioned inequality equation.
 i.e., 3n+2 ≤ c*n, now using trial and error, we find that for
c = 4 and above the equation satisfies.
 i.e., 3(n)+2 = 4*n
 Now find the value of n by putting n = 1, 2, 3 …
 So for n = 2 we see that 3(n)+3 = 4*n qualifies, therefore
declare that value of n as base value i.e., as n0.

You can find the example at this link: [Link]/watch?v=FEnwM-iDb2g

Asymptotic Notations

 Definition-2:
 f(x) = Ω(g(n)) – read as “f of n is omega of g of n.
 If there exists a positive integer n0 and a positive
number C such that |f(n)| ≥ c |g(n)|, for all n ≥ no
 E.g.,

f(n) g(n) Complexity

16n3 + 8n2 + 12 n3 f(n) = Ω(n3)
24n – 9 n f(n) = Ω (n)
Asymptotic Notations

 Definition-3:
 f(x) = θ(g(n)) – read as “f of n is theta of g of n.
 If there exists a positive integer n0 and two positive
constants C1 and C2 such that
 C1|g(n)| ≤ |f(n)| ≤ C2|g(n)|, for all n ≥ no
 E.g.,

f(n) g(n) Complexity

28n + 9 n f(n) = θ (n)
16n2 + 30n – 90 n2 f(n) = θ (n2)
7*2n + 30n 2n f(n) = θ(2n)
NOTE:

 The running time of algorithms are dependent on two factors:

 Size of the input
 Nature of the input, i.e., sorted, unsorted, processed or
unprocessed etc.
 In a sequential search for the first occurring of an even
number in a list of numbers:
 Best case: when the element is found at the first search
 Average case: the element could be found after almost
comparing with half of the elements
 Worst case: the element is found at the end of the array
or list
Growth Rate: Big O Notation

 The following are some of the standard growth rate functions:

 log2(n)
 n
 n log2(n)
 n2
 n3
 2n

Src:Data Strucutres by G A V Pai, Schaum’s Outlines

Growth Rate: Big O Notation

Src: Geeks for geeks

Growth Rate: Ω Notation

Src: Geeks for geeks

Growth Rate: θ Notation

Src: Geeks for geeks

Growth Rate: θ Notation
Measures of efficiency
Growth rate
Plot of efficiency measures