Design & Analysis of Algorithms

Lecture 3

Recurrence, Analysis of control

structures and few examples

Computer Science & Informatics department

 Today’s Lecture

Steps in the design and

analysis of an algorithm.
Analysis of Control Structures
Recursive calls
Few Analysis Examples

2
Major Stages of Algorithm Analysis and Design
• Every algorithm needs a process in order to be
created and utilized.

• FOUR steps of algorithm analysis and design:

1. Design

2. Analyze

3. Implement

4. Experiment
 Stage 1: Design
• Identify the problem and thoroughly
understand it.

• Consult with everybody who has an interest in

the problem.

• Break out problem into stages and calculate

what happens at each step so the next step
can occur.
• Flowcharts and/or pseudo codes used
 Stage 2: Analyze
• Analyzing how efficient the code is in solving
the problem.

• Efficiency of the algorithm.

• Algorithms are measured in time and space

for their efficiency.

• How your algorithm works with different size

data structures and what kind of time it takes
to work through those structures
 Stage 3: Implement
• Writing and coding the algorithm

• Write code to execute quickly and handle input

data

• Notate, comment code

 Stage 4: Experiment
• Once the algorithm is designed and coded
go back and experiment with different
variables in the algorithm.
• Try to make to make it fail

• Re-write the code to work it out most

efficiently.

• Keep attacking the efficiency aspect until it

executes as much data as necessary in the
smallest amount of time
 Characteristics of a good algorithm:
1) Precision – the steps are precisely stated(defined).

2) Uniqueness – results of each step are uniquely defined

and only depend on the input and the result of the
preceding steps.

3) Finiteness – the algorithm stops after a finite number of

instructions are executed.

4) Input – the algorithm receives input.

5) Output – the algorithm produces output.

6) Generality – the algorithm applies to a set of inputs.

Special classes of algorithms
• Order 1: O(1)
• Linear O(n)
• Logarithmic: O(log n)
• Quadratic O(n2)
• Polynomial O(n ), k 1
k

• Exponential O(a ), n> 1

n
9
Constant Time Complexity O(1)

• NO loop, NO recursion and NO

call to any other non-constant
time function

• i.e. set of non-recursive and non-

loop statements
 Constant Time Complexity O(1)
• Running time remains constant and does
NOT depend on the size of the input.
• Execution time of an O(1) algorithm will
always take the same amount of time
regardless of the input size.

• Example of an O(1) algorithm is accessing

an element in an array using an index.
 Linear Time Complexity O(n)
• The loop variables are
incremented/decremented by a constant
amount.
• Running time is proportional to the size of
the input
• Examples: Searching for an element in an
unsorted array or iterating through an array
and performing a constant amount of work
for each element, swap function.
 Quadratic Time Complexity O(n^2)
• Complexity proportional to the squared
size of the input data.

• For an input of size n, the algorithm

takes n * n steps to complete the
operation.

• Examples: nested loop, selection sort

and insertion Sort
Logarithmic Time Complexity O(Log n)
• The loop variables are
divided/multiplied by a constant
amount.

• Examples: Recursive calls in the

recursive function, binary search
Logarithmic Time Complexity O(Log Log n)

• The Time Complexity of a loop is

considered as O(Log Log n) if the
loop variables are
reduced/increased exponentially
by a constant amount.
Analysis of consecutive loops?
• complexity = sum of the time
complexities of individual loops.

• Multiply the no of iterations of each

loop by the time complexity of each
iteration and taking the maximum of
all possible combinations.
Analysis of consecutive loops?
for i in range(n):
for j in range(m):
# some constant time operation

• total time complexity is O(n * m)

Comparing the asymptotic running time
• An algorithm that runs in O(n) time is
better than one that runs in O(n2) time

• Similarly, O(log n) is better than O(n)

• Hierarchy of functions:
log n << n << n2 << n3 << 2n
18
Complexities in the order of their growth
rate
 An Example – Linear Search
INPUT: a sequence of n numbers, key to search for.
OUTPUT: true if key occurs in the sequence, false
otherwise.
LinearSearch(A, key) cost 
n
i 2
times
1

1 i1 c1 1
2 While i ≤ n and A[i] != key c2 n
3 do i++ c3 n-1
4 if i  n c4 1
5 then return true c5 1
6 else return false c6 1

So, the running time ranges between

c1+ c2+ c4 + c5 – best case
and
c1+ c2(n+1)+ c3n + c4 + c6 – worst case 20
 A Simple Example – Linear Search
INPUT: a sequence of n numbers, key to search for.
OUTPUT: true if key occurs in the sequence, false
otherwise.
LinearSearch(A, key) cost 
i 2
n times
1

1 i1 1 1
2 while i ≤ n and A[i] != key 1 n
3 do i++ 1 n-1
4 if i  n 1 1
5 then return true 1 1
6 else return false 1 1
Assign a cost of 1 to all statement executions.
Now, the running time ranges between
1+ 1+ 1 + 1 = 4 – best case
and
1+ (n+1)+ n + 1 + 1 = 2n+4 – worst case 21
 A Simple Example – Linear Search
INPUT: a sequence of n numbers, key to search for.
OUTPUT: true if key occurs in the sequence, false
otherwise.
LinearSearch(A, key) cost times

n

1 i1
1
1 i 2
1
2 while i ≤ n and A[i] != key 1 n
3 do i++ 1 n-1
4 if i  n 1 1
5 then return true 1 1
6 else return false 1 1
• If we assume that we search for a random item in the list,
on an average, Statements 2 and 3 will be executed n/2
times.
• Running times of other statements are independent of
input. Hence, average-case complexity is
1+ n/2+ n/2 + 1 + 1 = n+3 22
 Order of growth
• Principal interest is to determine
– how running time grows with input size – Order of growth.
– the running time for large inputs – Asymptotic complexity.

• In determining the above,

– Lower-order terms and coefficient of the highest-order term
are insignificant.
– Ex: In 7n5+6n3+n+10, which term dominates the running time
for very large n?

• Complexity of an algorithm is denoted by the highest-order

term in the expression for running time
– Ex: Ο(n), Θ(1), Ω(n2), etc.
– Constant complexity when running time is independent of the input
size – denoted Ο(1).
– Linear Search: Best case Θ(1), Worst and Average cases: Θ(n).
 Analysis of Loops
• Involves finding the number of operations
performed by a loop as a function of the
input size.

• Step 1: Determine the number of

iterations of the loop and the number of
operations performed in each iteration.
 Analysis of Loops
• no of iterations = loop
control variables and loop
termination condition
 Analysis of Loops
• Step 2: Express the total number of
operations performed by the loop as a
function of the input size.
– Use mathematical expressions or find a
closed-form expression
• Step 3: Determine the order of growth of the
expression for the number of operations
performed by the loop.
– Use Big O notation/dominant term
Analysis: A Harder Example

27
 Solution
• How do we analyze the running time of an
algorithm that has complex nested loop?
• The answer write out the loops as summations
and then solve the summations.
• To convert loops into summations, we
work from inside-out.

28
 Analysis: A Harder Example

It is executed for k = j, j − 1, j − 2, . . . , 0. Time

spent inside the while loop is constant. Let I() be
the time spent in the while loop 29
Analysis: A Harder Example

30
Analysis: A Harder Example

31
 Analyzing Control Structures
Summary
• Algorithm usually proceeds from the inside out

• First determine the time required by individual

instructions

• Second, combine the times according to the control

structures that combine the instructions in the program

• Some control structures sequencing are easy to

evaluate
• Others such as while loops are more difficult
32
Analyzing Control Structures Sequencing
• A sequence is a series of statements that do not alter the
execution path within an algorithm.

• Statements such as assign and add are sequence

statements.

• A call to another algorithm is also considered a sequence

statement.

• Selection statements evaluate one or more alternatives.

Paths are followed based on its result.

33
 Analyzing Control Structures Sequencing
• Let P1 and P2 be two fragments of an algorithm

• Let t1 and t2 be the times taken by P1 and P2 respectively

Sequencing Rule

• The time required to compute " P1 : P2 ", is simply t1+ t2.

• By the maximum rule, this time is in (max(t1, t2))

• It could happen that one of the parameters that control t2 depend

on the result of the computation performed by P1
• Thus analysis of "P1 : P2" cannot always be performed by
considering P1 and P2 independently
34
 Analyzing Control Structures:
Consider the loop
"For" loops
• for i ← 1 to m do P(i)

• Suppose the loop is part of a larger algorithm working on an

instance of size n. Let t denote the time required to compute
P(i)

• P(i) is performed m times, each time at a cost of t Total time

required by the loop is l = mt
If the time t(i) required for P(i) varies as a function of i, the
loop takes a time given by the sum

35
Analyzing Control Structures
for i ← 1 to m do P(i)

36
Analysing control structures: for
loops

37
Analysing of For Loop for Computing

38
While and Repeat Loops

39
While and Repeat Loops

40
 Difference in Analysis
for(i=0;i<m;i++) for(i=0;i<m;i++)
{}
for(j=0;j<n;j++) for(j=0;j<n;j++)
{ }
for(k=0;k<q;k++) for(k=0;k<q;k++)
{ } { }

O(n3) O(n)
41
RECURRENCE
 What is a recurrence relation?
• A recurrence relation, T(n), is a recursive function of integer
variable n.
• Like all recursive functions, it has both recursive case and base
case.
• Example:

• The portion of the definition that does not contain T is called the
base case of the recurrence relation
• The part that contains T is called the recurrent or recursive
case.
Forming Recurrence Relations
• For a given recursive method, the base case and the recursive case of its recurrence
relation correspond directly to the base case and the recursive case of the method.
• Example 1: Write the recurrence relation for the following method.

public void f (int n) {

if (n > 0) {
[Link](n);
f(n-1);
}
}

• The base case is reached when n == 0. The method performs one

comparison. Thus, the number of operations when n == 0, T(0), is some
constant a.
• When n > 0, the method performs two basic operations and then calls
itself, using ONE recursive call, with a parameter n – 1.
• Therefore the recurrence relation is:
Forming Recurrence Relations
Example 2: Write the recurrence relation for the following method.
public int g(int n) {
if (n == 1)
return 2;
else
return 3 * g(n / 2) + g( n / 2) + 5;
}

• The base case is reached when n == 1. The method performs one

comparison and one return statement. Therefore, T(1), is constant c.
• When n > 1, the method performs TWO recursive calls, each with the
parameter n / 2, and some constant # of basic operations.
• Hence, the recurrence relation is:
 Recursive vs Non-recursive algorithms
• A recursive function in general has an
extremely high time complexity while a
non-recursive one does not.
• A recursive function generally has smaller
code size whereas a non-recursive one is
larger.
• In some situations, only a recursive function
can perform a specific task, but in other
situations, both a recursive function and a
non-recursive one can do it.
Solving Recurrence Relations
 Solving a recurrence relation means obtaining a
closed-form solution .

 There are four methods to solve recurrence

relations that represent the running time of
recursive methods:
 Iteration method (unrolling and summing)
 Substitution method
 Recursion tree method
 Master method
Iteration method (unrolling and summing)
 Solving Recurrence Relations - Iteration
method- Useful Formulae
• Steps:
 Expand the recurrence
 Express the expansion as a summation by plugging the recurrence
back into itself until you see a pattern.
 Evaluate the summation
• In evaluating the summation one or more of the following summation formulae
may be used:
• 1. Arithmetic series:

•Special Cases of Geometric Series:

• 2. Geometric Series:
Solving Recurrence Relations - Iteration
method- Useful Formulae
• 3. Harmonic Series:

• 4. Others:
 Analysis Of Recursive Binary Search
public int binarySearch (int target, int[] array,
int low, int high) {
if (low > high)
return -1;
else {
int middle = (low + high)/2;
if (array[middle] == target)
return middle;
else if(array[middle] < target)
return binarySearch(target, array, middle + 1, high);
else
return binarySearch(target, array, low, middle - 1);
}
}
• The recurrence relation for the running time of the method is:
T(1) = a if n = 1 (one element array)
T(n) = T(n / 2) + b if n > 1
Analysis Of Recursive Binary Search
– Expanding:
T(n) = T(n / 2) + b
= [T(n / 4) + b] + b = T (n / 22) + 2b
= [T(n / 8) + b] + 2b = T(n / 23) + 3b
= ……..
= T( n / 2k) + kb

– When n / 2k = 1  n = 2k  k = log2 n, we have:

T(n) = T(1) + b log2 n

= a + b log2 n

– Therefore, Recursive Binary Search is O(log n)

 Tower of Hanoi
• Tower of Hanoi is a mathematical puzzle invented
by a French Mathematician Edouard Lucas in
1883.
• The game starts by having few discs stacked in
increasing order of size. The number of discs can
vary, but there are only three pegs.
 Tower of Hanoi
• The Objective is to transfer the entire tower to
one of the other pegs. However you can only
move one disk at a time and you can never stack
a larger disk onto a smaller disk. Try to solve it in
fewest possible moves.
 Tower of Hanoi
Solution
To get a better understanding for the general
algorithm used to solve the Tower of Hanoi, try to
solve the puzzle with a small amount of Disks, 3 or
4, and once you master that , you can solve the
same puzzle with more discs with the following
algorithm.
 Tower of Hanoi
Recursive Solution for the Tower of Hanoi with algorithm

public static void hanoi(int n, char BEG, char AUX, char END)
{
if (n == 1)
[Link](BEG + " --------> " + END);
else
{
hanoi(n - 1, BEG, END, AUX);

[Link](BEG + " --------> " + END);

hanoi(n - 1, AUX, BEG,END);

}
}
 Tower of Hanoi
• Explicit Pattern
Number of Disks Number of Moves
1 1
2 3
3 7
4 15
5 31

• Powers of two help reveal the pattern:

Number of Disks (n) Number of Moves
1 2^1 - 1 = 2 - 1 = 1
2 2^2 - 1 = 4 - 1 = 3
3 2^3 - 1 = 8 - 1 = 7
4 2^4 - 1 = 16 - 1 = 15
5 2^5 - 1 = 32 - 1 = 31
 Analysis Of Recursive Towers of Hanoi Algorithm

public static void hanoi(int n, char BEG, char AUX, char END){
if (n == 1)
[Link](from + " --------> " + to);
else{
hanoi(n - 1, BEG, END, AUX);
[Link](from + " --------> " + to);
hanoi(n - 1, END, AUX, BEG);
}
}

• The recurrence relation for the running time of the method

hanoi is:
T(n) = a if n = 1
T(n) = 2T(n - 1) + b if n > 1
 Analysis Of Recursive Towers of Hanoi
Algorithm
Expanding:
T(n) = 2T(n – 1) + b
= 2[2T(n – 2) + b] + b = 22 T(n – 2) + 2b + b
= 22 [2T(n – 3) + b] + 2b + b = 23 T(n – 3) + 22b + 2b + b
= 23 [2T(n – 4) + b] + 22b + 2b + b = 24 T(n – 4) + 23 b + 22b + 21b + 20b
= ……
= 2k T(n – k) + b[2k- 1 + 2k– 2 + . . . 21 + 20]

Géométric Séries
When k = n – 1, we have:

Therefore, The method hanoi is O(2n)