Algorithm ???
A precise, step-by-step sequence of instructions (steps)
accomplishing a well-defined task.
Algorithm
Algorithm is the specification of how an operation takes
place on an Abstract Data Type (ADT).
Properties of an algorithm
o Efficiency: It must solve with the least amount of
computational resources.
o Effectiveness: It must be possible to perform each step
exactly and in a reasonable amount of time.
o Feasibility: It must be possible to perform each
instruction.
o Correctness: It must compute correct answer to all
possible legal inputs.
o Language/Technology Independence: It must not
depend on any programming language/Technology.
o Completeness: It must solve the problem completely.
o Generality: Algorithm should be valid on all possible
inputs.
A “Good” Algorithm
At the design stage of solving a particular problem, there
are two conflicting goals. These are:
1. To design an algorithm that is easy to understand, code
and design.
2. To design an algorithm that makes efficient use of the
computer resources such as CPU and memory.
Inefficiency Syndrome: Redundant Computation
static final int a = 10;
static final int n = 1000;
public static void main(String…arg){
int x, y;
for(int i = 0; i < n; i++){ x = x + 3;
y = a * a * x;
}
sop(“n=”+n);
Solution for a Redundant Computation
static final int a = 10;
static final int n = 1000;
public static void main(String[]arg){ int x, y, z=a*a; for(int i
= 0; i < n; i++){ x = x + 3;
y = z * x;
} sop(“n=”+n);
Trade Off: Time and Space
Gaining one resource (efficiency) at the expense of losing
another (efficiency). In the above example, we “took” an
additional space for the variable z in order to gain speed of
execution.
Late Termination
public int search (int[] Arr, int key) {
int flag = 0;
for(j = 0; j < [Link]; j++)
if (Arr[j] == key) flag = 1;
return flag;
Late Termination: Solution
public int search (int Arr[], int key){
boolean flag = false;
for(j = 0; j < [Link] && !flag; j++)
if (Arr[j] == key) flag = true;
return flag;
Referencing an Array Element
static final int n = 1000;
static final int a = 900;
public int arrayRef(int Arr[]){
int x = 0;
for(j = 0; j < [Link]; j++)
x = x + Arr[a] + j;
return x;
Referencing… Solution
static final int n = 1000;
static final int a = 900;
public int arrayRef(int Arr[])
{ int x = 0, v= Arr[a];
for(j = 0; j < [Link]; j++)
x = x + v + j;
return x;
Efficiency of Algorithms
Running with the least number of computational resources
such as time, space, and Bandwidth.
Complexity/Analysis of Algorithms
o It is about determining how much computing time and
storage is required by the algorithm. In other words, it
allows us to predict the resource requirement of an
algorithm for a given environment.
o Helps us to choose the most efficient algorithm among a
list of alternatives solving the same problem
Time X Space
¡ Computational Time Complexity (CPU Time)
¡ Computational Space Complexity (memory usage)
!!!
Running time is usually treated as the most important since
computational time is the most precious resource in most
problem domains
Approaches
o Empirical: Analyze the time it takes to run the
corresponding program by trying it on different instances.
o Theoretical: Determine the quantity of resources
required mathematically (Execution time, memory space)
needed by the algorithm.
The Empirical Approach
o clock-time can vary based on many factors:
o Specific processor speed
o Current processor load
o Specific data for a particular run of the program
o Input Size
o Input Properties
o Operating Environment
The Theoretical Approach
o We better analyze an algorithm according to the number
of operations required, rather than according to an
absolute amount of clock time involved.
o This can show how an algorithm’s efficiency changes
according to the size of the input.
o Given an implementation of an algorithm, it is possible
to plot a graph of the time taken to run the algorithm for
different input sizes.
General Rules
1. Execution of one of the following operations takes
time 1:
a. Assignment Operation
b. Single Input/Output Operation
c. Single Boolean Operations
d. Single Arithmetic Operations
e. Function Return
2. 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.
General Rules …
3. Loops:
a) Running time for a loop is equal to the running time for
the statements inside the loop * number of iterations.
b) The total running time of a statement inside a group of
nested loops is the running time of the statements
multiplied by the product of the sizes of all the loops.
c) For nested loops, analyze inside out.
Ø Always assume that the loop executes the
maximum number of iterations possible.
4. 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.
Example 1
public int sum (int n){
int sum; sum = 0;
for(int i = 1; i <= n; i++)
sum = sum + i;
return sum;
Complexity of Example 1
Time Units to Compute
1 for the assignment statement: int sum=0 ¡ In the for
loop:
1 assignment i=1,
n+1 tests i<=n
n increments i++.
n loops of 2 units for an assignment, and an addition.
1 for the return statement.
------------------------------------------------------------------
T (n)= 1+1+n+1+n+2n+1 = 4n+4
Time Complexity of Algorithms
¡ Running “time”: Running time refers to the number of
operations that the algorithm need to perform of as a
function of the input data size.
¡ Growth rate: Takes running time function and find the
most dominant part by neglecting the terms which are less
discriminative. This is called the Big O of the algorithm.
Big O
A time complexity function f(n) is said to
be of O(g(n) (Order of g(n)) if and only if
f(n) <= c.g(n) for a certain constant c and
“sufficiently” large n.
Common Complexity Classes OR Growth Rates
Constant function: O(k) for a constant k
Logarithmic function: O(log(n))
Linear function: O(n)
O([Link](n))// Linearithmic
Polynomial function: O(n2), O(n3), etc
Exponential function: O(an)
Factorial function: O(n!)
Let f(n) = 2n + 1, then we can say that f(n) is O(n) because
2n + 1 <= c.n for a certain constant c and for “sufficiently”
large n.
Big O Example 2
sum = 0
for (int i= 0; i<= n-1; i++)
for(int j= 0; j<= n-1; j++)
sum = sum + a[i][j];
Big O Example 2: Running Time
1 assignment
1 assignment
N logical expression
2N arithmetic expression
N assignment N assignment
N2 logical expression
N2 arithmetic expression
N2 assignment
N2 assignment
è f(n) = 5n2 + 4n + 2
Big O Example 4
int sum = 0;
for(int i= 0; i<+ n-1; i++)
for(int j= 0; j<= i ; j++)
sum = sum +a[i][j];
Big O Example 4: Running Time & Growth Rate
f(n) = (n2 – n)/2
Since n2 is the dominant operation, f(n) is of O(n2).
Note: f(n) can not be bounded by a linear function g(n) = n for
sufficiently large n even if one can easily get a large constant
c for which f(n) <= c. n for “relatively small” n.
Big O Example 5
int sum = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < i * i; j++)
sum = sum + i*j;
Big O Example 5: Running Time & Growth Rate
f(n) = => 1/3n3 – 1/2n2 + 1/6n
Since n3 is the dominant operation, f(n) is of O(n3).
Note: f(n) can not be bounded by a quadratic function g(n) =
n2 for sufficiently large n even if one can easily get a large
constant c for which f(n) <= c. n2 for “relatively small” n.