CHAPTER 1 PART 2

INTRODUCTION

Data Structure
and Algorithm
DATA STRUCTURE AND ALGORITHM 1
PSEUDOCODE

 Informal language used to present algorithms.

 Pretty close to English but precise enough for a computing agent to carry out.

 High-level description of an algorithm

 More structured than English prose

 Less detailed than a program

 Preferred notation for describing algorithms

 Hides program design issues

header

DATA STRUCTURE AND ALGORITHM 3

Example: find max element of an array

Algorithm arrayMax(A, n)
Input array A of n integers
Output maximum element of A
currentMax  A[0]
for i  1 to n  1 do
if A[i]  currentMax then
currentMax  A[i]
return currentMax
PSEUDOCODE DETAILS

 Control flow  Method/Function call

 if … then … [else …] var.method (arg [, arg…])
 while … do …
 Return value
 repeat … until …
return expression
 for … do …
 Expressions
 Indentation replaces braces
¬ Assignment
 Method declaration
(linoe  in C++)
Algorithm method (arg [, arg…])
= Equality testing
Input … (linoe  in C++)
Output …
n2 Superscripts and other mathematical
formatting allowed
Algorithm 2
Algorithm 1 Algorithm 3

e ?
oo s
o ch
t
o ne
ich
Wh
Problem
Algorithm 5
Algorithm 4

Algorithm 7

Algorithm 6

DATA STRUCTURE AND ALGORITHM 6

ALGORITHM COMPLEXITY ANALYSIS

 How can we identify most efficient algorithm ?

 predicting the resources that the algorithm requires

 Time complexity: the amount of time taken by an algorithm to run as a function of the length of the

input.

 Space complexity: the amount of space or memory taken by an algorithm to run as a function of the

length of the input.

 Time/Space TRADE OFF :- we may have to sacrifice one at the cost of the other

 Time and space complexity depends on …. Hardware, OS, processors ..etc

 We only consider the execution time of an algorithm.

DATA STRUCTURE AND ALGORITHM 7
CONT.…

Efficiency of an algorithm can be analyzed at two different stages, before implementation and after
implementation.

 A Priori Analysis − This is a theoretical analysis of an algorithm.

 Efficiency of an algorithm is measured by assuming that all other factors, for example, processor speed, are

constant and have no effect on the implementation.

 A Posterior Analysis − This is an empirical analysis of an algorithm.

 The selected algorithm is implemented using programming language.

 This is then executed on target computer machine.

 In this analysis, actual statistics like running time and space required, are collected.
DATA STRUCTURE AND ALGORITHM 8
SPACE COMPLEXITY

 Analysis of space complexity of an algorithm or program is the amount of memory it

needs to run to completion.

 Some of the reasons for studying space complexity are:

1. To avoid failure/crash of algorithm after we implement it due to memory overflow

2. We may be interested to know in advance that whether sufficient memory is available to run the
program.

3. There may be several possible solutions with different space requirements.

4. Can be used to estimate the size of the largest problem that a program can solve
DATA STRUCTURE AND ALGORITHM 9
TIME COMPLEXITY

 The time complexity of an algorithm or a program is the amount of time it needs to run to

completion.

 The exact time will depend on

 the implementation of the algorithm, programming language, optimizing the capabilities of the compiler used,

the CPU speed, other hardware characteristics/specifications and so on.

 To measure the time complexity accurately, we have to count all sorts of operations performed in an

algorithm.

 If we know the time for each one of the primitive operations performed in a given computer, we can

easily compute the time taken by an algorithm to complete its execution.

our intention is to estimate the execution time of
DATA STRUCTURE AND ALGORITHM an algorithm irrespective of the computer machine 10

on which it will be used.

EXECUTION TIME CASES

 Worst-Case Analysis –The maximum amount of time that an algorithm require to solve a

problem of size n. This gives an upper bound for the time complexity of an algorithm.
 represents a guarantee for performance on any possible input.

 Best-Case Analysis –The minimum amount of time that an algorithm require to solve a

problem of size n. The best case behavior of an algorithm is NOT so useful.

 This gives an lower bound for the time complexity of an algorithm.

 Average-Case Analysis –The average amount of time that an algorithm require to solve a

problem of size n. Sometimes, it is difficult to find the average-case behavior of an algorithm.

 Worst-case analysis is more common than average-case analysis.
DATA STRUCTURE AND ALGORITHM 11
EXAMPLE

5 20 2 23 8 10 1

 Suppose you are given an array A and an integer x and you have to find if x exists in array
A.

for i : 1 to length of A
if A[i] is equal
to x
return
DATA STRUCTURE AND ALGORITHM 12

TRUE
return False
HOW TO ESTIMATE RUN TIME COMPLEXITY OF AN
ALGORITHM ?

 When we analyze algorithms, we should employ mathematical techniques (theoretical model) that

analyze algorithms independently of specific implementations, computers, etc...

 Before we can analyze an algorithm, we must have a model of the implementation technology that

will be used, including a model for the resources of that technology and their costs.

 We shall assume a generic one processor, random-access machine (RAM) model of computation

as our implementation technology and understand that our algorithms will be implemented as

computer programs.
DATA STRUCTURE AND ALGORITHM 13
RAM MODEL

 RAM is a hypothetical computer

 The RAM is a simple model of how computers perform.

 Instructions are executed one after another, with no concurrent operations.

 Under the RAM model, we measure the run time of an algorithm by counting up the number of

significant /basic / primitive operations in the algorithm.

 Then, we will express the efficiency of algorithms using growth functions.

 Each ``simple'' operation (+, *, -, =, if, call) takes exactly 1 time

 Each memory access takes exactly one time step, and we have as much memory as we need.

DATA STRUCTURE AND ALGORITHM 14

PRIMITIVE OPERATIONS

 Basic computations performed by an algorithm

 Identifiable in pseudocode

 Largely independent from the programming language

 Exact definition not important

 Assumed to take a constant amount of time in the RAM model

 Examples:

 Evaluating an expression, Assigning a value to a variable, Indexing into an array, Calling a method,

Returning from a method

DATA STRUCTURE AND ALGORITHM 15
GENERAL RULES FOR ESTIMATION

 We assume an arbitrary time unit.

 Execution of one of the following operations takes time 1:
 assignment operation
 single I/O operations
 single Boolean operations, numeric comparisons
 single arithmetic operations
 function return
 array index operations, pointer dereferences

DATA STRUCTURE AND ALGORITHM 16

GENERAL RULES FOR ESTIMATION

 Running time of a selection statement (if, switch) is the time for the condition evaluation +
the maximum of the running times for the individual clauses in the selection.
 The running time of a for loop is at most the running time of the statements inside the for
loop (including tests) times the number of iterations.
 Always assume that the loop executes the maximum number of iterations possible

 Running time of a function call is 1 for setup + the time for any parameter calculations +
the time required for the execution of the function body.

DATA STRUCTURE AND ALGORITHM 17

EXAMPLE

 By inspecting the pseudocode, we can determine the maximum number of primitive

operations executed by an algorithm, as a function of the input size
int count() Time Units to Compute

{ -------------------------------------------------

int no=0; 1 for the assignment statement: int no=0

1 for the output statement.
cout<< “Enter an
1 for the input statement.
integer”;
In the for loop:
cin>>n; 1 assignment, n+1 tests, and n increments.
for (i=0;i<n;i++) n loops of 2 units for an assignment, and an addition.
no=no+1; 1 for the return statement.
return 0; -------------------------------------------------------------------
} T (n)= 1+1+1+(1+n+1+n)+2n+1 = 4n+6 = O(n)
DATA STRUCTURE AND ALGORITHM 18
EXAMPLE
void func() Time Units to Compute
{ -------------------------------------------------
int x=0;
int i=0; 1 for the first assignment statement: x=0;
int j=1; 1 for the second assignment statement: i=0;
cout<< “Enter an Integer value”; 1 for the third assignment statement: j=1;
cin>>n;
1 for the output statement.
while (i<n)
{ 1 for the input statement.
x++; In the first while loop:
i++;
n+1 tests
}
while (j<n) n loops of 2 units for the two increment (addition) operations
{ In the second while loop:
j++;
n tests
}
} n-1 increments
DATA STRUCTURE AND ALGORITHM ------------------------------------------------------------------- 19

T (n)= 1+1+1+1+1+n+1+2n+n+n-1 = 5n+5 = O(n)

ASYMPTOTIC ANALYSIS

 Refers to defining the mathematical boundation/framing of its run-time performance.

 Using asymptotic analysis, we can very well conclude the best case, average case, and

worst case scenario of an algorithm

 Asymptotic analysis is input bound i.e., if there's no input to the algorithm, it is concluded

to work in a constant time.

 Other than the "input" all other factors are considered constant.

 generally a theoretical issue

DATA STRUCTURE AND ALGORITHM 20

ASYMPTOTIC NOTATIONS

 It is a simple way to represent the time complexity of an algorithm.

 In asymptotic notation, we use only the most significant terms to represent the time complexity of an

algorithm.

 Asymptotic Notation identifies the behavior of an algorithm as the input size changes.

 Following are the commonly used asymptotic notations to calculate the running time complexity of an

algorithm.
 Ο Notation (Big O) – Upper bound

 Ω Notation (Omega) – Lower bound

 θ Notation (Theta) – average bound

DATA STRUCTURE AND ALGORITHM 21
TYPES OF FUNCTIONS, LIMITS, AND SIMPLIFICATION

 These are some basic function growth classifications used in various notations.
 Logarithmic Function - log n
 Linear Function - an + b
 Quadratic Function - an2 + bn + c
 Polynomial Function - an^z + . . . + an^2 + a*n^1 + a*n^0, where z is some constant
 Exponential Function - a^n, where a is some constant

 The list starts at the slowest growing function (logarithmic, fastest execution time) and
goes on to the fastest growing (exponential, slowest execution time).

disregard constants, and lower order terms,

DATA STRUCTURE AND ALGORITHM
because as the input size (or n in our f(n) example) 22
increases to infinity (mathematical limits), the
lower order terms and constants are of little to no
BIG-O
 Big-O, commonly written as O, is an Asymptotic Notation for the worst case, or ceiling of

growth for a given function.

 It provides us with an asymptotic upper bound for the growth rate of runtime of an

algorithm.

 Say f(n) is your algorithm runtime, and g(n) is an arbitrary time complexity you are trying

to relate to your algorithm. f(n) is O(g(n)), if for some real constants c (c > 0) and n 0, f(n)

<= c g(n) for every input size n (n > n0).

DATA STRUCTURE AND ALGORITHM 23

EXAMPLE

 f(n)=10n+5 and g(n)=n. Show that f(n) is O(g(n)).

 To show that f(n) is O(g(n)) we must show that constants c and no such that

f(n) <=c.g(n) for all n>=no

Or 10n+5<=c.n for all n>=no
Try c=15. Then we need to show that 10n+5<=15n
Solving for n we get: 5<5n or 1<=n.
So f(n) =10n+5 <=15.g(n) for all n>=1.
(c=15,no=1).
DATA STRUCTURE AND ALGORITHM 24
EXAMPLE

 f(n) = 〖𝟑𝒏〗 ^𝟐+4n+1. Show that f(n)=O(𝒏^𝟐).

 4n <=4𝒏^𝟐 for all n>=1 and 1<=𝒏^𝟐 for all n>=1

〖 3𝑛 〗 ^2 +4n+1<=3𝒏^𝟐+4𝒏^𝟐+𝒏^𝟐 for all n>=1

〖 3𝑛 〗 ^2 +4n+1<=8𝒏^𝟐 for all n>=1
So we have shown that f(n)<=8𝒏^𝟐 for all n>=1
Therefore, f (n) is O(𝒏^𝟐) (c=8,k=1)

DATA STRUCTURE AND ALGORITHM 25

BIG-O TIME COMPLEXITY COMPARISON
O(1) < O(log n) < O(√n) < O(n) < O(n log n) < O(n 2) < O(n3)….. < O(2n) < O(3n)
…..< O(nn)

DATA STRUCTURE AND ALGORITHM 26

GROWTH-RATE FUNCTIONS

 O(1) Time requirement is constant, and it is independent of the problem’s size.

 O(log2n) Time requirement for a logarithmic algorithm increases slowly as the problem size
increases.
 O(n) Time requirement for a linear algorithm increases directly with the size of the problem.
 O(n*log2n) Time requirement for a n*log2n algorithm increases more rapidly than a linear
algorithm.
 O(n2) Time requirement for a quadratic algorithm increases rapidly with the size of the problem.
 O(n3) Time requirement for a cubic algorithm increases more rapidly with the size of the
problem than the time requirement for a quadratic algorithm.
 O(2n) As the size of the problem increases, the time requirement for an exponential algorithm
increases too rapidly to be practical.

DATA STRUCTURE AND ALGORITHM 27

A COMPARISON OF GROWTH-RATE FUNCTIONS

DATA STRUCTURE AND ALGORITHM 28

OMEGA NOTATION
 Big-Omega, commonly written as Ω, is an Asymptotic Notation for the best case, or a floor

growth rate for a given function.

 It provides us with an asymptotic lower bound for the growth rate of runtime of an

algorithm.

 f(n) is Ω(g(n)), if for some real constants c (c > 0) and n0 (n0 > 0), f(n) is >= c g(n) for

every input size n (n > n0)

DATA STRUCTURE AND ALGORITHM 29

EXAMPLE

 f(n) = 3n+2. Show that f(n)=Ω(n).

 C=1 & n0 >=1

DATA STRUCTURE AND ALGORITHM 30

THETA NOTATION

 Theta, commonly written as Θ, is an Asymptotic Notation to denote the asymptotically

tight bound on the growth rate of runtime of an algorithm.

 f(n) is Θ(g(n)), if for some real constants c1, c2 and n0 (c1 > 0, c2 > 0, n0 > 0), c1 g(n) is

< f(n) is < c2 g(n) for every input size n (n > n0).

 ∴ f(n) is Θ(g(n)) implies f(n) is O(g(n)) as well as f(n) is Ω(g(n)).

DATA STRUCTURE AND ALGORITHM 31

EXAMPLE

 f(n) = 3n+2. Show that f(n)= (n).

DATA STRUCTURE AND ALGORITHM 32