Introduction to

Analysis of Algorithms
 Introduction
• What is Algorithm?
– a clearly specified set of simple instructions to be followed to solve a
problem
• Takes a set of values, as input and
• produces a value, or set of values, as output
– May be specified
• In English
• As a computer program
• As a pseudo-code
• Data structures
– Methods of organizing data
• Program = algorithms + data structures
 Introduction
• Why need algorithm analysis ?
– writing a working program is not good enough
– The program may be inefficient!
– If the program is run on a large data set, then the
running time becomes an issue
 Example: Selection Problem
• Given a list of N numbers, determine the kth
largest, where k  N.
• Algorithm 1:
(1) Read N numbers into an array
(2) Sort the array in decreasing order by some
simple algorithm
(3) Return the element in position k
 Example: Selection Problem…
• Algorithm 2:
(1) Read the first k elements into an array and sort
them in decreasing order
(2) Each remaining element is read one by one
• If smaller than the kth element, then it is ignored
• Otherwise, it is placed in its correct spot in the array,
bumping one element out of the array.
(3) The element in the kth position is returned as
the answer.
 Example: Selection Problem…
• Which algorithm is better when
– N =100 and k = 100?
– N =100 and k = 1?
• What happens when N = 1,000,000 and k =
500,000?
• There exist better algorithms
 Algorithm Analysis
• We only analyze correct algorithms
• An algorithm is correct
– If, for every input instance, it halts with the correct output
• Incorrect algorithms
– Might not halt at all on some input instances
– Might halt with other than the desired answer
• Analyzing an algorithm
– Predicting the resources that the algorithm requires
– Resources include
• Memory
• Communication bandwidth
• Computational time (usually most important)
 Algorithm Analysis…
• Factors affecting the running time
– computer
– compiler
– algorithm used
– input to the algorithm
• The content of the input affects the running time
• typically, the input size (number of items in the input) is the main
consideration
– E.g. sorting problem  the number of items to be sorted
– E.g. multiply two matrices together  the total number of elements
in the two matrices
• Machine model assumed
– Instructions are executed one after another, with no concurrent
operations  Not parallel computers
 Worst- / average- / best-case
• Worst-case running time of an algorithm
– The longest running time for any input of size n
– An upper bound on the running time for any input
 guarantee that the algorithm will never take longer
– Example: Sort a set of numbers in increasing order; and the data is in
decreasing order
– The worst case can occur fairly often
• E.g. in searching a database for a particular piece of information
• Best-case running time
– sort a set of numbers in increasing order; and the data is already in
increasing order
• Average-case running time
– May be difficult to define what “average” means
 Running-time of algorithms
• Bounds are for the algorithms, rather than
programs
– programs are just implementations of an
algorithm, and almost always the details of the
program do not affect the bounds

• Bounds are for algorithms, rather than

problems
– A problem can be solved with several algorithms,
some are more efficient than others
 What is the efficiency of an
algorithm?
Run time in the computer: Machine Dependent
Example: Need to multiply two positive integers a and b

Subroutine 1: Multiply a and b

Subroutine 2: V = a, W= b
While W > 1
V →V + a; W →W-1
Output V
 Solution: Machine Independent
Analysis

We assume that every basic operation takes constant time:

Example Basic Operations:

Addition, Subtraction, Multiplication, Memory Access

Non-basic Operations:
Sorting, Searching

Efficiency of an algorithm is the number of basic

operations it performs
We do not distinguish between the basic operations.
Subroutine 1 uses ? basic operation
Subroutine 2 uses ? basic operations

Subroutine ? is more efficient.

This measure is good for all large input sizes

In fact, we will not worry about the exact values, but will
look at ``broad classes’ of values, or the growth rates
Let there be n inputs.
If an algorithm needs n basic operations and another
needs 2n basic operations, we will consider them to be in
the same efficiency category.
However, we distinguish between exp(n), n, log(n)
 Measuring Algorithm Efficiency
• Algorithm has both time and space requirements called complexity to
measure
• Types of complexity
– Space complexity
– Time complexity
• Analysis of algorithms
– The measuring of either time/space complexity of an algorithm
• Measure the time complexity since it is more important
• Cannot compute actual time for an algorithm.
• Give function of problem size that is directly proportional to time
requirement: growth-rate function
• Function measures how the time requirement grows as the problem
size grows.
– We usually measure worst-case time

14
Measuring Algorithm Efficiency

Three algorithms for computing

1 + 2 + … n for an integer n > 0

15
 Measuring Algorithm Efficiency

The number of operations required by the algorithms

16
Measuring Algorithm Efficiency

The number of operations required by the algorithms

as a function of n
17
 Big Oh Notation
• Computer scientists use a notation to
represent an algorithm’s complexity.
• To say "Algorithm A has a worst-case time
requirement proportional to n"
– We say A is O(n)
– Read "Big Oh of n" or “order of at most n”
• For the other two algorithms
– Algorithm B is O(n2)
– Algorithm C is O(1)

18
 Big Oh Notation
Grows in magnitude from left to right…

Tabulates magnitudes of typical growth-rate functions

evaluated at increasing values of n
When analyzing the time efficiency of an algorithm, consider
larger problems. For small problems, the difference between the
execution time is usually insignificant.
19
 Asymptotic Notation

Big-Oh
f(n) is O(g(n)) if f(n) is asymptotically less
than or equal to g(n)
Big-Omega
f(n) is (g(n)) if f(n) is asymptotically
greater than or equal to g(n)
Big-Theta
f(n) is (g(n)) if f(n) is asymptotically
equal to g(n)
Typical Growth Rates
 Picturing Efficiency

Body of loop requires a constant amount of time

O(1)
an O(n) algorithm.
22
Picturing Efficiency

An O(n2) algorithm. 23
Picturing Efficiency

Another O(n2) algorithm. 24

 You can go through

[Link]
o-big-omega-big-theta-49e7

[Link]
big-omega-and-big-theta/