Analysis of Algorithms
Dr. Bibhas Ghoshal
Assistant Professor
Department of Information Technology
Indian Institute of Information Technology Allahabad
Data Structures
Spring Semester 2022
Dr. Bibhas Ghoshal, IIIT Allahabad
Problem – Algorithm – Data Structures &
Techniques
Designing Algorithms: Many Algorithms can
Problem divided into exist to solve
sub-problems One problem
Solves
Problem Algorithm
( Ex: Searching) ( Ex: Binary Search)
Contains Uses
Specification Data Structure and Techniques
Input => Output Ex: Sorting is technique, Array is a Data Structure
Data Structures
Spring Semester 2022
Dr. Bibhas Ghoshal, IIIT Allahabad
Algorithm
Algorithm
●
Well-defined computational procedure for transforming inputs to outputs
Problem
●
Specifies the desired input output relationship
Correct Algorithm
●
Produces the correct output for every possible input in finite time -
Solves the problem
Data Structures
Spring Semester 2022
Dr. Bibhas Ghoshal, IIIT Allahabad
Algorithm Analysis
Predict resource utilization of an algorithm
●
Run-time
●
Memory
Dependent on architecture & model
●
Serial
●
Parallel
●
Quantum
●
---
Data Structures
Spring Semester 2022
Dr. Bibhas Ghoshal, IIIT Allahabad
Factors for Algorithm Design Consideration
●
Run-time
●
Space / Memory
●
Scalability
●
Guaranteeing correctness
●
Deterministic vs. Randomized
●
Computational model
●
System considerations: cache, disk, network speeds, etc.
●
Suitable to problem’s domain
Data Structures
Spring Semester 2022
Dr. Bibhas Ghoshal, IIIT Allahabad
Random Access (RAM) Model
Simple serial computing model
Model that we assume
Data Structures
Spring Semester 2022
Dr. Bibhas Ghoshal, IIIT Allahabad
What to Analyze?
●
Space complexity: storage requirement
●
Time complexity: computing time
Data Structures
Spring Semester 2022
Dr. Bibhas Ghoshal, IIIT Allahabad
Space Complexity
S(P)=C+SP(I)
Fixed Space Requirements (C) :
Independent of the characteristics of the inputs and outputs
instruction space
space for simple variables, fixed-size structured variable, constants
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
Data Structures
Spring Semester 2022
Dr. Bibhas Ghoshal, IIIT Allahabad
Space Complexity Analysis
Simple arithmetic function
float abc(float a, float b, float c)
{
return a + b + b * c + (a - c) / (a + b) + 4.00;
}
Variable Space requirement Sabc(I) = 0
Data Structures
Spring Semester 2022
Dr. Bibhas Ghoshal, IIIT Allahabad
Space Complexity Analysis
Iterative function for summing a list of numbers
float sum(float list[ ], int n)
{
float tempsum = 0;
int i;
for (i = 0; i<n; i++)
tempsum += list [i];
return tempsum;
}
Variable Space requirement Ssum(I) = 0
Data Structures
Spring Semester 2022
Dr. Bibhas Ghoshal, IIIT Allahabad
Space Complexity Analysis
Recursive function for summing a list of numbers
float rsum(float list[ ], int n)
{
if (n) return rsum(list, n-1) + list[n-1];
return 0;
}
Variable Space Requirement Ssum(I)=Ssum(n)=6n
Analysis of Space requirement per recursive call
Type Name Number of bytes
parameter: float list [ ] 2
parameter: integer n 2
return address:(used internally) 2(unless a far address)
TOTAL per recursive call 6
Data Structures
Spring Semester 2022
Dr. Bibhas Ghoshal, IIIT Allahabad
Time Complexity
T(P)=C+TP(I)
Compile Time (C) :
Independent of the instance characteristic
Execution Time / Run Time (TP(I)) :
depends on the instance characteristic (I)
Program Step :
syntactically or semantically meaningful program segment whose execution time is indepe
ndent of the instance characteristics
Example: float abc(float a, float b, float c)
{
return a + b + b * c + (a - c) / (a +b)+ 4.00;
}
TP(n)=caADD(n)+csSUB(n)+clLDA(n)+cstSTA(n)
Data Structures
Spring Semester 2022
Dr. Bibhas Ghoshal, IIIT Allahabad
Time Complexity
Methods to Compute Step Count :
1. Introduce variable Count into programs
2. Tabular method
Determine the total number of steps contributed by each statement
Step 1 : step per execution frequency
Step 2 : add up the contribution of all statements
Data Structures
Spring Semester 2022
Dr. Bibhas Ghoshal, IIIT Allahabad
Time Complexity Analysis
Count variable Method
// Iterative function for summing a list of numbers
float sum(float list[ ], int n)
{
float tempsum = 0;count = 0; // for assignment //
int i;
for (i = 0; i<n; i++)
count++; // for loop //
tempsum += list [i];count++; // for assignment //
count++; // last execution of for//
return tempsum;
Count++; // for return //
}
2n + 3 steps
Data Structures
Spring Semester 2022
Dr. Bibhas Ghoshal, IIIT Allahabad
Time Complexity Analysis
Tabular Method
Iterative function to sum a list of numbers
Statement s/e Frequency Total steps
float sum(float list[ ], int n) 0 0 0
{ 0 0 0
float tempsum = 0; 1 1 1
int i; 0 0 0
for(i=0; i <n; i++) 1 n+1 n+1
tempsum += list[i]; 1 n n
return tempsum; 1 1 1
} 0 0 0
Total 2n+3
Data Structures
Spring Semester 2022
Dr. Bibhas Ghoshal, IIIT Allahabad
Time Complexity Analysis
Tabular Method
Recursive function to sum a list of numbers
Statement s/e Frequency Total steps
float rsum(float list[ ], int n) 0 0 0
{ 0 0 0
if (n) 1 n+1 n+1
return rsum(list, n-1)+list[n-1]; 1 n n
return list[0]; 1 1 1
} 0 0 0
Total 2n+2
Data Structures
Spring Semester 2022
Dr. Bibhas Ghoshal, IIIT Allahabad
Time Complexity Analysis
Tabular Method
Matrix Addition
Statement s/e Frequency Total steps
Void add (int a[ ][MAX_SIZE]‧ ‧ ‧ ) 0 0 0
{ 0 0 0
int i, j; 0 0 0
for (i = 0; i < row; i++) 1 rows+1 rows+1
for (j=0; j< cols; j++) 1 rows‧ (cols+1) rows‧ cols+rows
c[i][j] = a[i][j] + b[i][j]; 1 rows‧ cols rows‧ cols
} 0 0 0
Total 2rows‧ cols+2rows+1
Data Structures
Spring Semester 2022
Dr. Bibhas Ghoshal, IIIT Allahabad
Do Constants matter?
What happens if :
●
N is small (< 100 ) ?
●
N is medium ( <1000,000 ) ?
●
N is large ( > 1,000,000 ) ?
Assymptotically, curves matter more than absolute values !!
●
Let :
T1(N) = 3N2 + 100N + 1
T2(N) = 50N2 + N + 500
● Compare T (N) and T (N)
1 2
Both curves would show Quadratic behaviour
Data Structures
Spring Semester 2022
Dr. Bibhas Ghoshal, IIIT Allahabad
The Assymptotic Notations
Notation Purpose Definition
O(n) Upper bound, possibly f(n) ≤ c g(n)
tight
Ω(n) Lower bound, possibly f(n) ≥ c g(n)
tight
ϴ(n) Tight bound c1 g(n) ≤ f(n) ≤ c2 g(n)
o(n) Upper bound, strict f(n) < c g(n)
ω(n) Lower bound, strict f(n) > c g(n)
Data Structures
Spring Semester 2022
Dr. Bibhas Ghoshal, IIIT Allahabad
The Assymptotic Growth
Data Structures
Spring Semester 2022
Dr. Bibhas Ghoshal, IIIT Allahabad
While Using Algorithmic Analysis
Algorithm’s Complexity
When asked to analyze an algorithm’s complexities:
1st Preference:
Whenever possible, use ϴ(n) [ Tight Bound ]
2nd Preference:
If not use O(n) or o(n) [ Upper Bound ]
3rd Preference:
If not use Ω(n) or ω(n) [ Lower Bound ]
Unless otherwise stated express an Algorithm’s complexity in terms
of its Worst case
Data Structures
Spring Semester 2022
Dr. Bibhas Ghoshal, IIIT Allahabad
Rule of Thumb for Algorithmic Analysis
Problem’s Complexity
The problem is as hard as........
Use Ω(n) or ω(n) [ Lower Bound ]
The problem cannot be harder ........
Use O(n) or o(n) [ Upper Bound ]
The problem is as hard as ........
Use ϴ(n) [ Tight Bound ]
Unless otherwise stated express an Algorithm’s complexity in terms
of its Worst case
Data Structures
Spring Semester 2022
Dr. Bibhas Ghoshal, IIIT Allahabad
Example for Big-Oh
c g(n) = n2
Let f(n)=10 n ==> f(n) = O(n2) f(n) = 10n
Proof:
If f(n) = O(g(n)) ==> f(n) ≤ c g(n)
for all n>n n
0
n0
n 10 n c n2
(show such a <c,n > combination exists)
0 (c=1)
==> c=1, n0 = 9
1 10 1
(try to find the lowest possible n0) 2 20 4
3 30 9
4 40 16
5 50 25
--- --- ---
9 90 81
10 100 100
Data Structures
Spring Semester 2022
Dr. Bibhas Ghoshal, IIIT Allahabad
Examples
3n+2 = O(n) /* 3n+2 4n for n = 2 */
3n+3 = O(n) /* 3n+3 4n for n= 3 */
100n+6 = O(n) /* 100n+6 101n for n = 10 */
10n2+4n+2 = O(n2) /* 10n2+4n+2 11n2 for n=5 */
6*2n+n2 = O(2n) /* 6*2n+n2 7*2n for n= 4 */
Data Structures
Spring Semester 2022
Dr. Bibhas Ghoshal, IIIT Allahabad
Some more Examples
N2 = O(N2) = O(N3) = O(2N)
N2 = Ω(1) = Ω(N) = Ω(N2)
N2 = Θ(N2)
N2 = o(N3)
2N2 + 1 = Θ(?)
N2 + N = Θ(?)
N3 - N2 = Θ(?)
3N3 – N3 = Θ(?)
Data Structures
Spring Semester 2022
Dr. Bibhas Ghoshal, IIIT Allahabad
Plot of some common functions
Data Structures
Spring Semester 2022
Dr. Bibhas Ghoshal, IIIT Allahabad
Reflexivity, Symmetry and Transitivity
Is f(n) = Θ(f(n)) ? Yes
Reflexive o(n), ω(n) – non Reflexive
Is f(n) = O(f(n)) ? Yes
Is f(n) = Ω(f(n)) ? Yes
-------------------------------------------------------------------------------------------
f(n) = O(g(n)) iff g(n) = Ω(f(n))
Transpose Symmetry
f(n) = o(g(n)) iff g(n) = (f(n))
----------------------------------------------------------------------------
f(n) = Θ(g(n)) and g(n) = Θ(h(n)) f(n) = Θ(h(n))
f(n) = O(g(n)) and g(n) = O(h(n)) ? Transitivity
f(n) = Ω(g(n)) and g(n) = Ω(h(n)) ?
Data Structures
Spring Semester 2022
Dr. Bibhas Ghoshal, IIIT Allahabad
Rules
Rule 1:
If T1(n) = O(f(n)) and T2(n) = O(g(n)), then
T1(n) + T2(n) = O(f(n) + g(n))
T1(n) * T2(n) = O(f(n) * g(n))
Rule 2:
T( n) is a polynomial of degree k, then T(n) = Θ(nk)
Rule 3:
logkn = O(n) for any constant k
Rule 4:
logan = (logbn) for any constants a & b
Data Structures
Spring Semester 2022
Dr. Bibhas Ghoshal, IIIT Allahabad
Some Proofs
Prove that : n log n = O(n2)
Proof :
log n <= n, for n >=1 ( considering n0 = 1)
Multiplying n on both sides :
n log n <= 1. n2
Data Structures
Spring Semester 2022
Dr. Bibhas Ghoshal, IIIT Allahabad
Some Proofs
Prove that : 6 n3 ≠ O(n2)
Proof :
By contradiction
If 6 n3 = O(n2)
6 n3 < = c n 2
6 n< = c
It is not possible to bound a variable with a constant
which is a Contradiction
Data Structures
Spring Semester 2022
Dr. Bibhas Ghoshal, IIIT Allahabad
