When faced with a problem:
1. First clearly define the problem
2. Think of possible solutions
3. Select the one that seems the best under the
prevailing circumstances
4. And then apply that solution
5. If the solution works as desired, fine; else go
back to step 2
An algorithm is a step-by-step procedure for
solving a particular problem in a finite amount of
time.
A computer program is an instance, or
concrete representation, for an algorithm in some
programming language
An input sequence is called an
instance of a Problem
Why Study Algorithms?
• For real-time problems, we would like to prove that
an algorithm terminates in a given time.
• Algorithm may indicate which the best and fastest
solution to a problem is without having to code up and
test different solutions.
Properties of Algorithms
• It must be composed of an ordered sequence of
precise steps.
• It must have finite number of well-defined
instructions /steps.
• The execution sequence of instructions should not
be ambiguous.
• It must be correct.
• It must terminate.
Why Algorithms are Useful?
• Once we find an algorithm for solving a problem, we
do not need to re-discover it the next time we are
faced with that problem
All the knowledge required for solving the problem is
present in the algorithm
Why Write an Algorithm Down?
• For your own use in the future, so that you don’t
have spent the time for rethinking it
• Written form is easier to modify and improve
• Makes it easy when explaining the process to others
Why Analysis of Algorithms?
• For real-time problems, we would like to prove that
an algorithm terminates in a given time.
• Algorithmic may indicate which the best and fastest
solution to a problem is without having to code up and
test different solutions
Importance of Analyzing
Algorithms?
• Need to recognize limitations of various algorithms
for solving a problem
• Need to understand relationship between problem
size and running time
• When is a running program not good enough?
• Need to learn how to analyze an algorithm's
running time without coding it
• Need to learn techniques for writing more efficient
code
What do we analyze about
Algorithms?
• Algorithms are analyzed to understand their
behavior and to improve them if possible
• Correctness
• Does the input/output relation match algorithm
requirement?
• Amount of Work Done
• Basic operations to do task
• Amount of Space Used
• Memory used
• Simplicity & Clarity
• Verification and implementation.
• Optimality
• Is it impossible to do better?
The efficiency of an algorithm
is a measure of the amount of resources consumed
in solving a problem of size n
• Running time (number of primitive steps that are
executed)
• Memory/Space
Computation Model for Analysis:
• To analyze an algorithm is to determine the
amount of resources necessary to execute it. These
resources include computational time, memory and
communication bandwidth.
• Analysis of the algorithm is performed with respect
to a computational model called RAM (Random
Access Machine)
• A RAM is an idealized uni-processor machine with
an infinite large random-access memory
• Instruction are executed one by one
• All memory equally expensive to access
• No concurrent operations
• Constant word size
• All reasonable instructions (basic operations) take
unit time
The complexity of an algorithm is the amount
of resources the algorithm performs to
complete its task.
Empirical analysis:
• Program the algorithm and measure its running
time on example
Instances
• Theoretical analysis
• Employ mathematical techniques to derive a
function which relates the running time to the
size of instance
Limitations of Empirical Analysis
• Implementation dependent
• Execution time differ for different
implementations of same program
• Platform dependent
• Execution time differ on different architectures
• Data dependent
• Execution time is sensitive to amount and type
of data manipulated.
• Language dependent
• Execution time differ for same code, coded in
different languages
∴ absolute measure for an algorithm is not
appropriate
Theoretical Analysis
• Data independent
• Takes into account all possible inputs
• Platform independent
• Language independent
• Implementation independent
• Not dependent on skill of programmer
• can save time of programming an inefficient solution
• Characterizes running time as a function
of input size, n.
Easy to extrapolate without risk
An elementary operation is an operation
which takes constant time regardless of problem
size.
Components of Algorithm:
• Variables and values
• Instructions
A linear sequence of elementary
operations is also performed in
constant time.
• Selections
• Repetitions
Any loop has two parts:
• How many iterations are performed?
• How many steps per iteration?
Two reasons why we are interested
in asymptotic growth rates:
• Practical purposes: For large problems, when we
expect to have big computational requirements
• Theoretical purposes: concentrating on growth
rates frees us from some important issues:
• fixed costs (e.g. switching the computer on!), which may
dominate for a small problem size but be largely irrelevant
• Machine and implementation details
• The growth rate will be a compact and easy to understand
the function
Running time is how long it takes a program to
run.
Time complexity is a description of the
asymptotic behavior of running time as input size
tends to infinity.
Data structure is the logical or mathematical
model of a particular organization of data.
Data structures let the input and output be
represented in a
With all these weaknesses, our
model is not so bad because?
• We have to give the comparison, not absolute
analysis of any algorithm.
• We have to deal with large inputs not with the small
size
• Model seems to work well describing
computational power of modern nonparallel
machines
Can we do Exact Measure of Efficiency?
• Exact, not asymptotic, measure of efficiency can be
sometimes computed but it usually requires certain
assumptions concerning implementation
The growth of the complexity functions is
what is more important for the analysis.
Asymptotic growth rate is a suitable measure
for the comparison of algorithms with increasing input
size n.
Asymptotic Notations Properties
• Categorize algorithms based on asymptotic growth
rate
• E.g. linear, quadratic, exponential
• Ignore small constant and small inputs
• Estimate upper bound and lower bound on growth
rate of time complexity function
• Describe running time of algorithm as n
Limitations
• Not always useful for analysis on fixed-size inputs.
• All results are for sufficiently large inputs.
Set is a collection of not ordered, not repeated
elements
Big-Oh Notation (O)
Intuitively:
Set of all functions whose rate of growth is the same
as or lower than that of g (n). F (n) is bounded above
by g (n) for all sufficiently large n
Big-
Intuitively:
Set of all functions whose rate of growth is the same
as or higher than that of g (n).
the duality rule:
t(n f(n f(n t(n))
Intuitively:
Set of all functions that have same rate of growth as g
(n).
When a problem is (n), this represents both an upper
and lower bound i.e. it is O (n) and (n) (no algorithmic
gap)
Asymptotic Functions Summary
grow at the same rate, asymptotically
If f(n) = O(g(n)) and f(n) ≠ Ω(g(n)), then we
say that f(n) is asymptotically slower
growing than g(n).
If f (n) = Ω (g (n)) and f (n) ≠ O(g(n)), then
we say that f (n) is asymptotically faster
growing than g(n).
Insertion Sort: Suitable only for small n ≤ 50
or nearly sorted inputs
Merge Sort: Guaranteed to be fast even in its
worst case; stable
Heap Sort: Requiring minimum memory and
guaranteed to run fast; average and maximum
time both roughly twice the average time of
quick sort. Useful for time-critical applications
Quick Sort: Most useful general-purpose
sorting for very little memory requirement and
fastest average time. (Choose the median of
three elements as pivot in practice
Counting Sort: Very useful when the keys
have small range; stable;memory space for
counters and for 2n records.
Radix Sort: Appropriate for keys either rather
short or with a lexicographic collating sequence.
Bucket Sort: Assuming keys to have uniform
distribution.
