DATA STRUCTURES
AND ALGORITHMS
Complexity Analysis/Algorithm Analysis
What will be discussed
To review the concept of algorithm
Comparison of algorithm
Time complexity
Analysis of time complexity
Analysis of Algorithms
An algorithm is a finite set of precise instructions for
performing a computation or for solving a problem.
What is the goal of analysis of algorithms?
To compare algorithms mainly in terms of running time
but also in terms of other factors (e.g., memory
requirements, programmer's effort etc.)
How do we compare algorithms?
We need to define a number of objective
measures.
Compare execution times?
Not good: times are specific to a particular
computer !!
Count the number of statements executed?
Not good: number of statements vary with the
programming language as well as the style of the
individual programmer.
An Example of Algorithm Analysis:
Example
50 packages delivered to 50 different houses
50 houses one mile apart, in the same area
FIGURE 1-1 Gift shop and each dot representing a house
(Continue…)
Example (cont’d.)
Driver picks up all 50 packages
Drives one mile to first house, delivers first package
Drives another mile, delivers second package
Drives another mile, delivers third package, and so on
Distance driven to deliver packages
1+1+1+… +1 = 50 miles
Total distance traveled: 50 + 50 = 100 miles
FIGURE 1-2 Package delivering scheme
(Continue…)
Example (cont’d.)
Similar route to deliver another set of 50 packages
Driver picks up first package, drives one mile to the first
house, delivers package, returns to the shop
Driver picks up second package, drives two miles, delivers
second package, returns to the shop
Total distance traveled
2 * (1+2+3+…+50) = 2550 miles
FIGURE 1-3 Another package delivery scheme
(Continue…)
Example (cont’d.)
n packages to deliver to n houses, each one mile apart
First scheme: total distance traveled
1+1+1+… +n = 2n miles
Function of n
Second scheme: total distance traveled
2 * (1+2+3+…+n) = 2*(n(n+1) / 2) = n2+n
Function of n2
Time Complexity
In computer science, the time complexity of an
algorithm quantifies the amount of time taken by an
algorithm to run as a function of the length of the
string representing the input (Wikipedia)
Time Complexity
In other word, It is simple measurement of how fast
time taken by a program grows, if the input size ‘n’
and time ‘t’ then t is directly proportional to ‘n’
Example
What is prime number?
2,3,5,7,11,… *takes 1ms for division operation
Student 1: Student 2:
For i 2 to n-1 For i 2 to √ n
If ‘i’ divides ‘n’ If ‘i’ divides ‘n’
Then ‘n’ is not prime Then ‘n’ is not prime
In worst condition max division In worst condition max division will
will be (n-2) be (√ n-1)
1) n = 11 9ms 1) n=11 2ms
2) n =101 99ms 2) n=101 9ms
(Continue…)
So we realize through this example that the
correctness of the program is not the only thing
What also important for large number of input sizes
We should always try to write a program that
behaves well for large inputs
How to analyze Time Complexity?
Running time depends ( few more factors may
depends )
Single processor / Multi processor [X]
Read / Write speed onto memory [X]
32 bit / 64 bit architecture[X]
What input is given to program[√]
In time complexity we do not bother above factor
except of input how program behave with various
inputs
Mostly, we are interested in the rate of growth time
taken with respect to input
Calculation of rate of growth of
time an Algorithm
Now, calculate an expression that gives us the rate of growth
of time of an algorithm with respect to input
Firs we define Model Machine ( Hypothetical model machine
with below characteristics)
Single processor machine
32 bit
Execute instructions in program sequentially
Lets assume the machine takes 1unit of time all arithmetical,
logical operation, assignment to variable and return to the
function
* All other cost are negligible
Exmaple1(Pseudo-code)
Let’s we write a program
sum ( a , b )
{
return a + b ;
}
Run this program using model machine
Total time will be 2 units ( 1 return & 1 for arithmetic
operation)
tsum = 2, time taken is constant and it called
constant time algorithm
Exmaple2(Pseudo-code)
Sum of All elements
sumOfList( A , n ) Cost #of Time
{
1. total = 0 1unit/c1 1
2. for i=0 to n-1 2 unit/c2 n+1(1extra for false cond.)
3. total = total + Ai 2unit/c3 n
4. return total 1unit/c4 1
}
Total cost tsum = 4n + 4
Absolute term T(n) = c n + c’ where c = c2 + c3
And c’ = c1 + c2 + c4
Continue…
Constant are not imporant and we are not
interested only we are interesed in rate of growth
of th time taken and this case clearly the time
taken grows as a linear function simply because it’s
proportional to ‘n’
In first tsum = k
Second tsumoflist = cn + c’
In two dimensional matrix
tsumofmatrix = an2 + bn +c
Continue…
If we look at a graph
Clearly, for higher value of ‘n’, rate of growth of
the quadratic function is a lot more than the rate of
growth of a linear function
We often classify these function in the set where the
rate of growth of all the function in a particular set
is very similar
Continue…
For example Big-O of
O(n2) will define a set of all functions of the form of
an2 + bn +c
O(n) will define a set of all functions of the form of
cn +c’
O(1) will define a set of all functions of the form of
constants (k)
Conclusion
This classification of functions into these sets is done
using the concept of asymptotic bounds which is very
fundamental concept of in time complexity analysis
Big-O is actually called Asymptotic notation and also
we have some other Asymptotic notation called theta
Big-ɵ and Big-Ω
We will learn in a next lesson
Conclusion
In this Lecture we discussed…
What is an algorithm?
How can we compare different algorithms?
What is Time complexity?
How can we analyze an algorithm?
What is Big-O?
ANY QUERY ?
Practice Questions
