Data Structures and Algorithms
(ESO207)
Lecture 3:
• Time complexity, Big “O” notation
• Designing Efficient Algorithm
• Maximum sum subarray Problem
1
Three algorithms
Algorithm for F()mod No. Instructions in RAM model
RFib(,)
IterFib(,)
Clever_Algo_Fib(,) 35 + 11
• Which algorithm turned out to be the best ?experimentally ?
2
Lesson 1
from Assignment 1 ?
No. of instructions executed by
algorithm in RAM model
Prop
or ?
ti on al to
Time taken by algorithm
in real life
May
be diffe
?
rent
for d
iffer
ent i
np ut Dependence on input
3
Time complexity of an algorithm
Definition:
the worst case number of instructions executed
as a function of the input size (or a parameter defining the input size)
The number of bits/bytes/words
Examples to illustrate input size :
Problem Input size
Computing F()mod for any positive integers and bits
Whether an array storing numbers (each stored in a word) is sorted ? words
Whether a matrix of numbers (each stored in a word) contains “14” ? words
Homework: What is the time complexity of Rfib, IterFib, Clever-Algo-Fib ?
4
Example:
Whether an array A storing numbers (each stored in a word) is sorted ?
IsSorted(A)
{ ; time
flag true; time
while( and flag==true)
{
If (A[]< A[]) flagfalse ; times in the worst case
;
}
Return flag ; time
}
Time complexity =
5
Example:
Time complexity of matrix multiplication
Each element of the matrices
Matrix-mult(C[],D[]) occupies one word of RAM.
{ for to times
{ for to times
{ M[] ;
for to
{ M[] M[] + C[]*D[]; instructions
}
}
}
Return M time
}
Time complexity =
6
Lesson 2 learnt from Assignment 1 ?
Algorithm for F()mod No. of Instructions
RFib(,)
IterFib(,)
Clever_Algo_Fib(,) 35 + 11
100 1000
Question: What would have been the outcome if
No. of instructions of Clever_Algo_Fib(,) = 100 + 1000
Answer: Clever_Algo_Fib would still be the fastest algorithm ...for large value of .
7
COMPARING EFFICIENCY OF ALGORITHMS
8
Comparing efficiency of two algorithms
Let A and B be two algorithms to solve a given problem.
Algorithm A has time complexity : 2 + 125
Algorithm B has time complexity : 5 + 67 + 400
Question: Which algorithm is more efficient ?
Obviously A is more efficient than B
9
Comparing efficiency of two algorithms
Let A and B be two algorithms to solve a given problem.
Algorithm A has time complexity : 2 + 125
Algorithm B has time complexity : 50 + 125
Question: Which one would you prefer based on the efficiency criteria ?
Answer : A is more efficient than B for < 25
B is more efficient than A for > 25
Time complexity is
really an issue only
when the input is of
large size
10
Rule 1
Compare the time complexities of two algorithms for
asymptotically large value of input size only
11
Comparing efficiency of two algorithms
Algorithm B with time complexity 50 + 125
is certainly more efficient than
Algorithm A with time complexity : + 125
12
A judgment question for you !
Algorithm A has time complexity f()= + + 1250
Researchers have designed two new algorithms B and C
• Algorithm B has time complexity g() = + 10
• Algorithm C has time complexity h() = + 20 + 2000
Which of B and C is an
improvement over A in the
true sense ?
= 1/5 = 0?
C is an improvement over A
in the true sense.
13
Rule 2
An algorithm X is superior to another algorithm Y if
the ratio of time complexity of X and time complexity of Y
approaches 0 for asymptotically large input size.
14
Some Observations
Algorithm A has time complexity f()= + + 1250
Researchers have designed two new algorithms B and C
• Algorithm B has time complexity g() = + 10
• Algorithm C has time complexity h() = + 20 + 2000
Algorithm C is the most efficient of all.
Observation 1:
multiplicative or additive Constants do not play any role.
Observation 2:
The highest order term governs the time complexity asymptotically.
15
ORDER NOTATIONS
A mathematical way
to capture the intuitions developed till now.
(reflect upon it yourself)
16
Order notation
Definition: Let f() and g() be any two increasing functions of n.
f() is said to be of the order of g()
if there exist constants c and such that
f() ≤ c g() for all n >
c g()
f()
𝑛0
If f() is of the order of g(), we
write f() = O(g()) 17
Order notation :
Examples
• 20 = O() 20, 1
• 100 = O() Loose 1, 160
160, 1
• = O() Loose While analyzing time complexity of an
algorithm accurately, our aim should be to
• 2000 = O(1) choose the g() which is NOT loose.
Later in the course, we shall refine & extend
Simple observations: this notion suitably.
If f() = O(g()) and g() = O(h()), then
f() = O(h())
If f() = O(h()) and g() = O(h()), then f() + g() =
?
O(h())
These observations can be helpful for simplifying time complexity.
Prove these observation as Homeworks
18
A neat description of time complexity
• Algorithm B has time complexity g() = + 10
Hence g() = O()
• Algorithm C has time complexity h() = + 20 + 2000
Hence h() = O()
• Algorithm for multiplying two matrices has time complexity
+ + 1 = O()
Homeworks:
• g() = , f() = . Is f() = O(g()) ? Give proof.
• What is the time complexity of selection sort on an array storing n elements ?
• What is the time complexity of Binary search in a sorted array of n elements ?
19
HOW TO DESIGN EFFICIENT ALGORITHM ?
(This sentence captures precisely the goal of theoretical computer science)
20
Designing an efficient algorithm
Facts from the world of algorithms:
1. No formula for designing efficient algorithms.
2. Every new problem demands a fresh approach.
3. Designing an efficient algorithm or data structure requires
1. Ability to make key observations.
2. Ability to ask right kind of questions.
3. A positive attitude and …
4. a lot of perseverance.
We shall demonstrate the above facts
during this course many times.
21
Max-sum subarray problem
Given an array A storing n numbers,
find its subarray the sum of whose elements is maximum.
4 7
A 3 -5 3 8 2 -4 9 -6 3 -2 -8 3 -5 1 7 -9
18 -2
22
Max-sum subarray problem:
A trivial algorithm
A_trivial_algo(A)
{ max A[0];
For i=0 to n-1
For j=i to n-1
{ temp compute_sum(A,i,j);
if max< temp then max temp;
}
return max;
} Homework: Prove that its
time complexity is O()
compute_sum(A, i,j)
{ sumA[i];
For k=i+1 to j sum sum+A[k];
return sum;
} 23
Max-sum subarray problem:
Question: Can we design O() time algorithm for Max-sum subarray problem ?
Answer: Yes.
Think over it with a fresh mind ….
We shall design it together in the next class…
24
