Unit – 1
Analysis of Algorithm
Algorithm
• An Algorithm is a sequence of
steps to solve a problem.
• In other words, an Algorithm is
defined as a collection of
unambiguous instructions
occurring in some specific
sequence and produces output
for a given set of inputs some
finite amount of time.
From Coremen
• “ An algorithm is well-defined computational procedure that takes
some value, or set of values as input and produces some value, or set
of values as output. “
• Thus an algorithm is a sequence of computational steps that
transform the input into the output.
Properties of Algorithm
1. Non-ambiguity
2. Range of Input
3. Multiplicity
4. Speed
5. Finiteness
Non-ambiguity Multiplicity
• Each step in algorithm should be non- • The same algorithm can be represented in
ambiguous. several different ways. i.e. for solving same
problem we may be able to write several
• Each instruction should be clear and precise. different algorithms.
• Any instruction should not have any conflicting • For example, to search number from the given
meaning. list we can either use "SEQUENTIAL SEARCH"
• This property also indicates "effectiveness" of method or "BINARY SEARCH" method.
algorithm.
Finiteness
• The algorithm should be finite. i.e. after performing required operations it should
be terminated.
Speed Range of Input
• The algorithm are written using some specific • The range of input should be specified.
ideas (popularly known as logic).
• Normally algorithm is input driven and if range
• The logic of the algorithm should be written in of input is not specified, then algorithm may
such a way that it can produce output with fast go in infinite state.
speed, thus, it should be "efficient".
Analysis of an Algorithm
• Analysis of an algorithm means to find out the resources required by
an algorithm.
• Resources of an algorithm may be:
• Time
• Space
• Power consumption
• Communication Bandwidth
• Computer Hardware, etc.
• It usually involves determining a function that relates the length of
algorithm input to no. of steps it takes (TIME COMPLEXITY) or no. of
storage (SPACE COMPLEXITY) locations it uses.
Complexity
TIME COMPLEXITY SPACE COMPLEXITY
Time complexity of an Space complexity of an
algorithm signifies the total algorithm signifies the total
time required by the program amount of memory or
to run till its completion. storage an algorithm needs.
Best Case Complexity
• " If an algorithm takes minimum time to solve the problem for
a given set of input, it is called best case time complexity. “
• For example, Suppose we want to search an element from the
list, and the element is found at first location, then only one
comparison is required (linear search). So, it is called best case
time complexity.
• So, best case time complexity of linear search is O(1).
Average Case Complexity
• "In an algorithm takes average amount of time to solve the
problem for given set of input, then it is called average case
time complexity.“
• Average case occurs with some random sequence of input
data.
• Average case analysis gives general behavior of an algorithm.
• For example, In linear search average case occurs when
required element is neither at first location nor at last location
but it is somewhere at in between position.
• Average case time complexity of linear search is O(n+1)/2 or
Worst Case Complexity
• "If an algorithm takes maximum time to solve the problem for
given set of input, it is called worst case time complexity. “
• For example, Suppose we want to search an element from the
list, and the element is found at the last location (or not found
at all) then we have to perform n comparison, where n is the
size of the list. So, it is called worst case time complexity.
• Worst Case Time Complexity of linear search is O(n).
Thank
You
