"Dream no small dreams for they have

no power to move the hearts of men."

11
…Goethe
CHAPTER

Algorithm Analysis

Learning Objectives
After reading this chapter, you will know:
1. Definition of Algorithm
2. Need for Analysis
3. Algorithm Analysis
4. Asymptotic Notation
5. Recurrence

Introduction
Once an algorithm is given for a problem and decided to be correct, then an important step is to
determine how much in the way of resources, such as time or space, the algorithm will be required.
The analysis required to estimate use of these resources of an algorithm is generally a theoretical
issue and therefore a formal framework is required. In this framework, we shall consider a normal
computer as a model of computation that will have the standard repertoire of simple instructions
like addition, multiplication, comparison and assignment, but unlike the case with real computer, it
takes exactly one unit time to do anything (simple) and there are no fancy operations such as matrix
inversion or sorting, that clearly cannot be done in one unit time. We always assume infinite
memory also.

Definition of Algorithm
An Algorithm is a finite sequence of instructions that, if followed, accomplishes a particular task. In
addition, all algorithms must satisfy the following criteria:
1. Input: Zero or more quantities are externally supplied.
2. Output: At least one quantity is produced.
3. Definiteness: Each instruction is clear and unambiguous.
4. Finiteness: If trace out the instructions of an algorithm, then for all cases, the algorithm
terminates after a finite number of steps.
5. Effectiveness: Every instruction must be very basic so that it can be carried out, in principle, by
a person using only pencil and paper. It is not enough that each operation be definite as in
criteria 3; it also must be feasible.

Algorithm Development Stages

There are five phases of Algorithm Development Stages:
(i) Requirements: Make sure you that we understand the information that is given (the input) and
what results that are produce (the output)
info@[Link] ©Copyright reserved. Web:[Link] 1
 Algorithm Analysis

(ii) Design: For each object there will be some basic operations to perform on it. These operations
already exist in the form of procedures and write an algorithm which solves the problem
according to the requirements.
(iii) Analysis: Can we think of another algorithm? If so, write it down. Next, try to compare these two
methods. It may already be possible to tell if one will be more desirable than the other. If you
can’t distinguish between the two, choose one to work on for now and we will return to the
second version later.
(iv) Refinement and Coding: Modern approach suggests that all processing which is independent of
the data representation be written out first.
(v) Verification: Verification consists of three distinct aspects;
(1) Program Proving, (2) Testing and (3) Debugging

Need for Analysis

Analysis is the study we perform in order to figure out what to do. It uses a high-level description of
the algorithm instead of an implementation and it characterizes running time as function of the
input size, n. it takes into account all possible inputs and allows us to evaluate the speed of an
algorithm independent of the hardware/software environment.
The “Analysis” deals with performance evaluation (Complexity Analysis). One of the goals of
analysis is to compare algorithm mainly in terms of running time but also in terms of other factors
(e.g., memory requirements, programmer’s effort etc.)

Algorithm Analysis
Types of Analysis/Behavior of Algorithm
Worst Case
 Provides an upper bound on running time
 An absolute guarantee that the algorithm would not run longer, no matter what the inputs are
Best Case
 Provides a lower bound on running time
 Input is the one for which the algorithm runs the fastest
Average Case
 Provides a prediction about running time
 Assumes that the input is random
 ower ound unning Time pper ound

The following two components need to be analyzed for determining algorithm efficiency. If we have
more than one algorithms for solving a problem then we really need to consider these two before
utilizing one of them.

Time Complexity
The time complexity of an algorithm is to find the time taken by an Algorithm to complete its
execution. There two methods
1. A Priori Analysis: It is based on determining the order of the magnitude of the statement,
construct or data structure. This method is independent of machine, programming language

info@[Link] ©Copyright reserved. Web:[Link] 2

 Algorithm Analysis

and operating system. If algorithm has to be analyzed further in detail then each operation
(Arithmetic, Relational and Logical) is considered to take 1 unit of time.
2. Posteriori Testing: In this method an algorithm is converted into a program using any
programming language, executed on a particular machine. Algorithm’s execution time is taken
with the systems watch time. Result of this analysis will be dependent on the machine and
language used. It will be real time.
Running Time Complexity: The time required for running an algorithm.

Space Complexity
The amount of space required at run-time by an algorithm for solving a given problem.
In general these measurements are expressed in terms of asymptotic notations, like Big-Oh, Theta,
Omega etc.

General Rules for Space Complexity Calculation

While computing space complexity we need to analyze whether the memory requirement is
dependent on input size. Three things mainly need to be considered;
1) Maximum width of system stack which holds the activation records during the run time of the
function.
2) Whether the size of activation record is dependent on input size.
3) And in each invocation how much memory is being used from heap.
Then space complexity is as follows:
Max-system-stack-width*((Size of the memory allocated on activation record which is
dependent on n )+ (Size of the memory allocated from heap which is dependent on n ))

Example: Consider the simple program fragment for analyzing space complexity.
int sum(int n)
{
int partialSum = 0;
for(int i = 0; i<n; i++)
partialSum = partialSum i i i;
return partialSum;
}
Notice that the memory used by this program is absolutely independent of input size
because this is non-recursive program and has only one activation record to be pushed on
the system stack whose size is not going to change with n and also each invocation
doesn’t have any heap space requirement which is dependent on n. So whether n = 10,
20, 100, etc, the number of records to be pushed is O (1). Therefore Space Complexity is O
(1).

Example: Consider the recursive C program which prints the null terminated string in the reverse
order.
void printRev(char *str)
{
if( *str == ‘\0’) return;

info@[Link] ©Copyright reserved. Web:[Link] 3

 Algorithm Analysis

printRev(str+1);
printf(“%c”,*str);
}
Maximum width of the system stack is O(L) where L is string length. And the size of
activation record is constant w.r.t length L. Therefore, space complexity is O(L).

General Rules for Running Time Calculations

Rule 1-for/While Loops
The running time of a for/while loop is = (The number of iteration perform)
(the running time of statements inside the loop).

Example: Consider the simple program fragment whose running time cost is O(n) where n is a
positive integer.
int sum(int n)
{
int partialSum = 0;
for (int i = 1; i<= n; i++)
partialSum = partialSum i i i;
return partialSum;
}
Lines 1 and 4 count one unit each. Line 3 counts for four units per time executed
(two multiplications, one addition, and one assignment) and is executed n times, for a
total of 4n units. Line 2 has hidden costs of initializing i, testing i <= n and incrementing i.
The total cost of all these is 1 to initialize, n+1 for all the tests, and n for all the
increments, which 2n+[Link], total cost of 6n+4, which is O(n).

Rule 2 –Nested loops

The total running time of a statement inside a group of nested loops is the running time of
the statement multiplied by the product of the sizes of all loops.
As an example following program fragment is O(n2).
for( i = 0; i< n ; i++)
for( j = 0; j<n; j++)
k++;

Rule 3 - Consecutive Statements

Just add running time of all these statements.

As an example, the following program fragment, which has O(n) work followed by O(n2)
work, is also O(n2).
for( i = 0; i< n ; i++)
k++;
for( i = 0; i< n ; i++)
for( j = 0; j<n; j++)
k++;

info@[Link] ©Copyright reserved. Web:[Link] 4

 Algorithm Analysis

Rule 4 – if/else
For the fragment
if (condition )
S1
else
S2
Running time of an if/else statement is never more than the running time of test plus the
larger of the running times of S1 and S2.

Rule 5 – Recursive function

Deriving the recurrence relation and then solving it for getting the running time is always
the better way than any other solution.

Example: Consider the code given below for printing null terminated string in reverse order.
Let T (n) be the running time of printRev ( ) for which string length is n. Then, T(n )
would represent running time of the same function which is given string of length n – 1.
Thus
T(n) = T(n 1) + O(1)

Logarithm Time Complexity

There are several algorithms, which require logn cost in worst case. Binary Search, Heap ADT
operations, etc are examples of that.
Typically, an algorithm is O (logn) if it takes constant time to cut the problem size by a half. That’s
what exactly happens in binary search algorithm.
int binarySearch(int a[ ], int len, int x)
{
int low = 0 , high = len – 1;
while(low < = high)
{
int mid = (low + high)/2;
if( a[mid] < x)
low = mid + 1;
else if(a[mid] > x)
high = mid – 1;
else
return mid;
}
return NOT_FOUND;
}

At first look this algorithm gives the illusion of O (n) cost as we might think that since it has a while
loop and that will always run for the entire length of the given array. A careful examination would
expose that the loop will not run more than O (logn) times since in each iteration high or low getting
adjusted such that the problem size decreases by half of the current size. The following recurrence

info@[Link] ©Copyright reserved. Web:[Link] 5

 Algorithm Analysis

relation can best represent the running time of binary search algorithm. T (n) = T (n/2) + 1, where
T (n) be the running time for n input elements.
Look at another interesting code given below.
sum = 0;
for( i = 1; i< n ; i)
sum++;
The i variable values getting incremented in each iteration such that its becoming double of current
hence certainly would not take much longer than logn to reach its value as n or more.

Amortized Analysis
An amortized analysis is any strategy for analyzing a sequence of operations to show that the
average cost per operation is small, even though a single operation within the sequence might be
expensive. Even though we take averages, however, probability is not involved. An amortized
analysis guarantees the average performance of each operation in the worst case.

Types of Amortize Analysis

There are three common amortization arguments:
 The Aggregate method.
 The Accounting method and
 The Potential method.

Online Algorithm
Definition: An algorithm that must process each input in turn, without detailed knowledge of future
inputs. In computer science, an online algorithm is one that can process its input piece-by-piece in a
serial fashion, i.e., in the order that the input is fed to the algorithm without having the entire input
available from the start. In contrast, an offline algorithm is given the whole problem data from the
beginning and is required to output an answer which solves the problem at hand (for example,
selection sort requires that the entire list be given before if can sort it, while insertion sort doesn’t).
Since it does not know the whole input, an online algorithm is forced to make decisions that may
later turn out not be optimal, and the study of online algorithms has focused on the quality of
decision-making that is possible in this setting. Competitive analysis formalizes this idea by
comparing the relative performance of an online and offline algorithm for the same problem
instance.

A problem exemplifying the concepts of online algorithms is the Canadian Traveler Problem, The
goal of this problem is to minimize the cost reaching a target in weighted graph where some of the
edges are unreliable and may have been removed from the graph. However, that an edge has been
removed (failed) is only revealed to the traveler when she/he reaches one of the edges endpoints.

The worst case for this problem is simply that all of the unreliable edges fail and the problem
reduces to the usual shortest path problem. An alternative analysis of the problem can be made with
the help of competitive analysis, for this method of analysis. The offline algorithm known in advance
which edges will fail and the goal is to minimize the ratio between the online and offline algorithm
performance. This problem is PSPACE-complete.

info@[Link] ©Copyright reserved. Web:[Link] 6

 Algorithm Analysis

Randomized Algorithm
In order to use probabilistic analysis, we need to know something about the distribution on the
inputs. In many cases, we know very little about the input distribution. Even if we do know
something about the distribution, we may not be able to model this knowledge computationally. Yet
we often can use probability and randomness as a tool for algorithms.

Consider the hiring problem. In the hiring problem, it may seem as if the candidates are being
presented to use in a random order, but we have no way of knowing whether or not they really are.
Thus, in order to develop a randomized algorithm for the hiring problem, we must have greater
control over the order in which we interview the candidates. We will, therefore, change the model
slightly. We will say that the employment agency has n candidates, and they send us a list of the
candidates in advance. On each day, we choose, randomly, which candidate to interviews. Although
we know nothing about the candidates (beside their names), we have made a significant change.
Instead of relying on a guess that the candidates will come to us in a random order, we have instead
of relying on a guess that the candidates enforced a random order. More generally, we call an
algorithm randomized if its behavior is determined not only by its input but also by values produced
by a random-number generator. We shall assume that we have at our disposal a random-number
generator RANDOM.

A call to RANDOM (a, b) returns an integer between a and b, inclusive, with each such integer being
equally likely.
For example, RANDOM (0, 1) produces 0 with probability 1/2, and it produces 1 with probability
1/2. A call to RANDOM (3, 7) retunes either3, 4, 5, 6 or 7, each with probability 1/5. Each integer
returned by RANDOM is independent of the integers returned on previous calls. You may imagine
RANDOM as rolling a (b a )-sided die to obtain its output.

Asymptotic Notation
 Asymptotic analysis is based on two simplifying assumptions which hold in most (but not all
cases). But it is important to understand these assumptions and limitations of asymptotic
analysis.
 Large input sizes: We are most interested in how the running time grows for large values of n
 Ignore constant factors: The actual running time of the program depends on various constant
factors in the implantations (coding tricks, optimizations in compilations speed of the
underlying hardware etc.) Therefore we will ignore constant factors.

The asymptotic notations are used to represent the relative growth rate between functions.

Big Oh (‘O’)
Represent upper bound on the running time and the memory being consumed by the algorithms.
O (n) essentially conveys that the growth rate of running time/memory consumption rate will not
be more than “n” for all inputs of size n for a given algorithm. However, it may be less than this.
More formally Big-Oh is defined as follows:
The function f(n) = Og(n) if and only if f(n) c. g(n) for all n, n n where c, n are positive
constants.

info@[Link] ©Copyright reserved. Web:[Link] 7

 Algorithm Analysis

Thus, if f(n) = O g(n) statement is said to be true then the growth rate of function g(n) is surely
higher than/equal to f(n).
We use O-notation to denote an upper bound that is not asymptotically tight
O (g (n)) = {f(n) : for any positive constant c > 0
There exists constant n0 > 0 0 f(n) cg(n) such that for all n n0+

Big-Oh Properties
1. If f (n) is O (g (n)) then a. f (n) is also O (g (n))
2. If f (n) is O (g (n)) and h (n) is O(p(n)) then f (n) + h(n) =O (max (g (n), P (n)))
3. If f (n) is O (g (n)) and h (n) is O (p (n)) then f (n) h (n) is O (g (n). p (n))
4. If f (n) is O (g (n)) and g (n) is O (h (n)) then f (n) is also O (h (n))
5. logn is O (logn) k
6. If f(n) is any polynomial of degree m, F(n) = a . n a n a n a , then f(n) is
O(n )

Θ Notation
C g(n)

f (n)

C g(n)

n
n0
f(n) = (g(n))
 For a given function g(n), we denote by Θ(g(n)), the set of functions:
Θ (g(n)) = {f(n): there exists positive constants c1, c2
And n0 such that 0 c g(n) f(n) c (g(n))
For all n n0
 Used when asymptotic lower bound is needed
Ω (g (n)) ={f(n): there exists positive constants c and
n such that 0 cg (n) f(n)
 Theorem
For any two functions f (n) and g (n) we have f (n) = Θ (g(n)) if and only
if f(n) = O(g(n)) and f (n) = Ω (g(n))

Remarks
 If f (x) = (g(x)) then g( x) is also (f(x))
 If f (x) = (g(x)) we can say that f (x) is O (g(x)) and f (x) is Ω (g(x)) and also g(x) is
O (f(x)) and g(x) is Ω (f(x))

info@[Link] ©Copyright reserved. Web:[Link] 8

 Algorithm Analysis

Small Oh (o)
The function f (n) = o (g(n)) iff
im f(n)
=o
n g(n)

Big Omega ( )
Big Omega represents lower bound on the running time and the memory being consumed by the
algorithms. Ω (n) essentially conveys that the growth rate of running time/memory consumption
rate will not be less than “n” for all inputs of size n for a given algorithm. However, it may be greater
than this.
More formally Big-Omega is defined as follows:
If f(x) and g (x) are any two functions and f (x) is Ω(g (x)),
If f (x) c. g(x) for x k where c and k are any two positive constants.
Thus, if f(x) is Ω(g (x)), statement is said to be true then the growth rate of function g(x) is surely
lower than/equal to f(x).

Small omega (ω) Notation

ω (g(n)) = *f(n) for any positive constant
c > 0 there exists a constant n > 0 such that
f (n) cg (n) ∀ n n }

Asymptotic form Relationship

f(n) ∈ (g(n)) f(n) = g(n)
f(n) ∈ Ο(g(n)) f(n) g(n)
f(n) ∈ Ω (g(n)) f(n) g(n)
f(n) ∈ ο(g(n)) f(n) < g(n)
f(n) ∈ ω(g(n)) f(n) > g(n)

Properties of Asymptotic Notations

1. Transitivity
f(n) = (g(n))and g(n) = (h(n))imply f(n) = (h(n)),
f(n) = O (g(n))and g(n) = O(h(n))imply f(n) = O(h(n)),
f(n) = Ω (g(n))and g(n) = Ω(h(n))imply f(n) = Ω(h(n)),
f(n) = o (g(n))and g(n) = o(h(n))imply f(n) = o(h(n)),
f(n) = ω (g(n))and g(n) = ω(h(n))imply f(n) = ω(h(n)),

2. Reflexivity
f(n) = (f(n)),
f(n) = O (f(n)),
f(n) = Ω (f(n)).

3. Symmetry
f(n) = (g(n))if and only if g(n) = (f(n)).

info@[Link] ©Copyright reserved. Web:[Link] 9

 Algorithm Analysis

4. Transpose Symmetry
f(n) = O (g(n)) if and only if g(n) = Ω(f(n)),
f(n) = O (g(n)) if and only if g(n) = ω(f(n)).
because these properties hold for asymptotic notations, one can draw an analogy between the
asymptotic comparison of two functions f and g the comparison of two real numbers a and b.
f(n) = O (g(n)) a b,
f(n) = Ω (g(n)) a b,
f(n) = (g(n)) a = b,
f(n) = o (g(n)) a b,
f(n) = w(g(n)) a b
We say that f (n) is asymptotically smaller than g (n) if f (n) = o (g(n)), and f (n) is
asymptotically larger than f (n) if f (n) = ω (g (n)).
One property of real numbers, however, does not carry over to asymptotic notation:

5. Trichotomy: For any two real numbers a and b, exactly one of the following must hold:
a < b, a = b, or a>b.

Some Examples
Example: f(n) = n
n n for all n
n = O (n)Here c = , n =

Example: f(n) = n n
n n n for n
n n = O (n )Here c = , n =

Example: f(n) = . n
. n
. n = O( ) for n

Example: n n O(n)
ecause here doesn’t exist any positive n and c so that Big-Oh equation gets satisfied.
Remarks - For the function 4n+3, 4n+3 is O(n)
4n+3 is also O(n ) and O(n )
Even though 4n+3 is O(n ) and O(n ) but the best answer for , 4n+3 is O(n) only, as
O(n) shows most tighter upper bound than the other in the question

Example: F (n) = n , h (n) = logn

n logn = O(n )
In general one should remember order of the following functions which will help while
solving the relative growth rate of more complicated functions.
O( )O(logn), O(n)O(nlogn), O(n ), O(n ) … . O(n ), O( )
All the functions are arranged in increasing order of growth rate.

info@[Link] ©Copyright reserved. Web:[Link] 10

 Algorithm Analysis

If an algorithm has the time complexity O(1), then the time complexity is said to be
constant, that means running time is independent of input size.

Example: f(n) = n
n n for n
n n for n
n is Ω (n) Here c = 2, k = 1
We can also say that n n for then c = 1, k = 1
Remarks:
If f(n) is O (g (n)), then g (n) is Ω(f (n)).

Example: f(n) = n2 + n + 1; g(n) = 5n2 + 1; h(n) = 2logn + n2

Then, f(n) = (g(n)) because both have same degree and hence will have same growth
rate.
f(n) = (h(n)) statement is also true because both have same degree and hence will have
same growth rates.
h(n) can be simplified as follows:
2logn is n only,
Let 2logn = n ---------> 1
By taking log on both sides in equation 1.
logn*loge2 = logen
Then, after simplifying the above equation
logn = logen/ loge2 = logn.
Therefore, h (n) = n + n2.

Recurrence
A recurrence is an equation or inequality that describes a function in terms of its value on smaller
inputs.

Three Methods of Recurrence

 Substitution method
The steps involved
1. Guess the form of solution
2. Use mathematical induction
 Recursion - tree method
This method converts the recurrence into a tree whose nodes represent the costs incurred at
various levels of recursion
 Master Method
n
T(n) = aT ( ) f(n)
b
Where a ,b and f(n) is a given function

info@[Link] ©Copyright reserved. Web:[Link] 11

 Algorithm Analysis

Master Theorem
T(n) = aT ( ) (n log n)
Where a ,b , k > 0 and p is a real number
1. If a>b , them T(n) = (n
k )
2. If a = b k

(a) If p > , then T(n) = (n log n)

(b) If p = , then T(n) = (n log log n)
(c) If p < , then T(n) = (n )
3. If a < b k

(a) If p 0, then T(n) = (n log n)

(b) If p < 0, then T(n) = Ο(n )

Example: T(n) = T(n ) n

Solution: T(n) = (n ) (Master Theorem case 3(a))

Example: T(n) = T(n ) n

Solution: T(n) = (n log n) (Master Theorem case 2(a))

Example: T(n) = 0. T(n )

Solution: Does not apply a

info@[Link] ©Copyright reserved. Web:[Link] 12