Data Structures
BITS Pilani CS01 Algorithm Analysis
Pilani|Dubai|Goa|Hyderabad
ALGORITHM
An algorithm is a finite set of instructions or logic, written in
order, to accomplish a certain predefined task. Algorithm is
not the complete code or program, it is just the core
logic(solution) of a problem, which can be expressed either
as an informal high level description as pseudocode or
using a flowchart.
Every Algorithm must satisfy the following properties:
1.Input- There should be 0 or more inputs supplied
externally to the algorithm.
2.Output- There should be atleast 1 output obtained.
3.Definiteness- Every step of the algorithm should be clear
and well defined.
4.Finiteness- The algorithm should have finite number of
steps.
2
5. Correctness- Every
Object Oriented step of
Programming the16,algorithm
, Lecture 30-07-2022 must
BITS Pilani, Pilani Campus
ALGORITHM
Performance Analysis
An algorithm is said to be a good algorithm if the following
conditions are satisfied:
1. Does the algorithm work as we expect?
2. Does the algorithm work correctly according to original
specification of the problem?
3. Does it have the documentation which is useful to the
users?
4. Does it in the codable form?
5. Does it take less time to execute ?
6. Does it occupy less space in the memory / storage area?
The last two criteria are used for judging the performance of
the algorithm. The performance of the algorithm is identified
as Time Complexity and Space Complexity.
3
Object Oriented Programming , Lecture 16, 30-07-2022
Limitations of experimental studies
Write a program implementing the algorithm.
Run the program with inputs of varying size and composition.
Use a method like System.currentTimeMillis() to get an accurate measure
of the actual running time.
Implementation is a must.
Execution is possible on limited set of inputs.
If we need to compare two algorithms we need to use the same
environment
(like hardware, software etc)
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Analytical model to analyze algorithm
Algorithm should be analyzed by using general
methodology.
This approach uses:
– High level description of the algorithm.
– Takes into account all possible inputs.
– Allows one to evaluate the efficiency of any algorithm in a way that is
independent of the hardware and the software environment.
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
methodology
for algorithm analysis.
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
methodology
for algorithm analysis.
Pseudo-code is a mixture of natural language and high-
level programming constructs that describe the main
ideas behind a generic implementation of a data
structure or algorithm
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Recurrence relations
Recursive Functions
void Test(int n)
{
if (n>0)
{ printf (“%d”,n);
Test (n-1);
}
}
T(n) =
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Techniques
We need techniques that enable us to compare algorithms without
implementing them.
Our two most important tools are
(1) the RAM model of computation and
(2) asymptotic analysis of worst-case complexity.
Running time depends upon.
☐ single vs multi-processor
☐ read/ write speed to memory
☐ 32-bits vs 64-bits
☐input: rate of growth of time algorithm.
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
The Random Access Machine
(RAM) Model (*)
• The RAM is a simple model of how computers perform.
A 32 bits CPU that supports sequential execution 2
A potentially unbounded bank of memory cells, each 1
0
of which can hold an arbitrary number or character
Memory cells are numbered and accessing any cell in memory
takes unit time.
1 unit time for assignment and return & 1 unit time for arithmetical and
logical operation
• Under the RAM model, we measure the run time of an algorithm by
counting up the number of steps it takes on a given problem
instance.
• By assuming that our RAM executes a given number of steps per
second, the operation count converts easily to the actual run time
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Primitive Operations
• Basic computations performed by an algorithm
• Identifiable in pseudocode
• Largely independent from the programming language
• Exact definition not important (we will see why later)
• Assumed to take a constant amount of time in the RAM model
• Primitive operations include the following: .
• Assigning .a value to a variable
• Calling a method
• Performing an arithmetic operation (for example, adding two
numbers).
• Comparing two numbers
• Indexing, into an array
• Following an object reference
• Returning, from a method.
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
RAM MODEL
Each ``simple'' operation (+, *, -, =, if, call) takes exactly 1
time step.
Loops and subroutines are not considered simple
operations. Instead, they are the composition of many
single-step operations.
The time it takes to run through a loop or execute a
subprogram depends upon the number of loop iterations.
Each memory access takes exactly one time step, and we
have as much memory as we need.
The RAM model takes no notice of whether an item is in
cache or on the disk, which simplifies the analysis.
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Time
Space
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Time
Space
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
methodology
for algorithm analysis.
The array-maximum problem is the simple problem of
finding the maximum element in an array A storing n
integers
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
methodology
for algorithm analysis.
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
methodology
for algorithm analysis.
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
methodology
for algorithm analysis.
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Running Time
best case
What is best, average, worst case running of a average case
problem? worst case
120
Average case time is often difficult to determine100
– why?
Running Time
80
We focus on the worst case running time. 60
Easier to analyze and best to bet 40
Crucial to applications such as games, 20
finance and robotics
0
• we need to determine how long the algorithm 1000 2000 3000 4000
takes, in terms of the size of its input. I nput Size
• The running time of the algorithm as a function
of the size of its input.
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Rate of Growth
Now focus on how fast a function grows with the input size.
We call this the rate of growth of the running time.
To keep things manageable, we need to simplify the function to keep
the most important part and cast aside the less important parts.
For example, suppose that an algorithm, running on an input of size n,
takes 5n^2 + 101n + 600
Compare 5n2 and 101n+600 as the value of n grows
By dropping the less significant terms and the constant coefficients,
we can focus on the important part of an algorithm's running time—
its rate of growth
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Rate of Growth ≡Asymptotic Analysis
• Using rate of growth as a measure to compare different
functions implies comparing them asymptotically.
• If f(x) is faster growing than g(x), then f(x) always
eventually becomes larger than g(x) in the limit (for
large enough values of x).
Time
Space
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Time
Space
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Time
Space
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Time
Space
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
“Better” = more efficient
Time
Space
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
“Better” = more efficient
Time
Space
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
“Better” = more efficient
Time
Space
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
“Better” = more efficient
Time
Space
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
“Better” = more efficient
Time
Space
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
“Better” = more efficient
Time
Space
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
“Better” = more efficient
Time
Space
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
“Better” = more efficient
Time
Space
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
“Better” = more efficient
Time
Space
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
“Better” = more efficient
Time
Space
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
“Better” = more efficient
Time
Space
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
“Better” = more efficient
Time
Space
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Time Complexity- Why should
we care?
Student 1 Student 2
for i 2 to n-1 for i 2 to √n [ till the square
If i divides n root of n]
n is not prime if i divides n
------------------------------------- n is not prime
I ms for a division in worst -------------------------------------
case (n-2) times. Worst case
n =11 ------? 9ms (√n-1) times
n = 101 -------? 99ms (3-1) = 2ms
(√101-1) times = 9ms
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Example 1
To find the sum of two numbers
Sum(a+b)
{
Return a+b
}
Tsum = 2 { it’s a constant time algorithm)
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Example 2
To find the sum of integers
Sum of list(A,n)
{
1. Total = 0
2. For i=0 to n-1
3. Total = total +A;
4. Return total
}
Tsum of list = 1+2(n+1)+2n+1
= 4n+4
T(n) = cn+c’
Where c= c2+c3
c’ = c1+c2+c4
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Example (Cont..,)
Tsum of matrix
Y
Tsum of list
Tsum
X (n-input size)
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Example
• Suppose you are designing a web site to
process user data (e.g., financial records).
• Suppose program A takes fA(n)=30n+8
microseconds to process any n records, while
program B takes fB(n)=n2+1 microseconds to
process the n records.
• Which program would you choose, knowing
you’ll want to support millions of users?
Visualizing Orders of Growth
• On a graph, as
you go to the
right, a faster fA(n)=30n+8
Value of function
growing
function
eventually fB(n)=n2+1
becomes
larger...
Increasing n
More Examples …
• We say that n4 + 100n2 + 10n + 50 is of
the order of n4 or O(n4)
• We say that 10n3 + 2n2 is O(n3)
• We say that n3 - n2 is O(n3)
• We say that 10 is O(1),
• We say that 1273 is O(1)
methodology
for algorithm analysis.
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Big-O Notation
• We say fA(n)=30n+8 is order n, or O(n).
It is, at most, roughly proportional to n.
• fB(n)=n2+1 is order n2, or O(n2). It is, at
most, roughly proportional to n2.
• In general, an O(n2) algorithm will be
slower than O(n) algorithm.
• Warning: an O(n2) function will grow
faster than an O(n) function.
Computing running time
Algorithm 1 Algorithm 2
Cost Cost
arr[0] = 0; c1 for(i=0; i<N; i++) c2
arr[1] = 0; c1 arr[i] = 0; c1
arr[2] = 0; c1
...
arr[N-1] = 0; c1
----------- -------------
c1+c1+...+c1 = c1 x N (N+1) x c2 + N x c1 =
(c2 + c1) x N + c2
O(n)
Computing running time (cont.)
Cost
sum = 0; c1
for(i=0; i<N; i++) c2
for(j=0; j<N; j++) c2
sum += arr[i][j]; c3
------------
c1 + c2 x (N+1) + c2 2x N x (N+1) + c3 x N x N
O(n )
Thank You!!
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
