FEDERAL UNIVERSITY GASHUA

FACULTY OF SCIENCE
DEPARTMENT OF COMPUTER SCIENCE

COURSE CODE: CPS 305

COURES TITLE: ALGORITHMS ANALYSIS AND COMPLEXITY
CREDIT UNIT: 3 Units
Course Outline

 Basic algorithm analysis

 Asymptotic analysis of upper (Big Oh) and average (Big Theta) complexity bounds

 Standard Complexity Class time and Space tradeoffs in algorithm analysis

 Recursive Algorithm (Divide and Conquer Algorithms)

 Algorithm strategies:

i. Fundamental computing algorithms

ii. Numerical algorithms

iii. Sequential and binary search algorithms

iv. Sorting algorithms

v. Binary search trees

vi. Hash tables

vii. Graph and its Representation

Text Book:

Aho A. Hopcroft J., and Ullman, J. The Design and Analysis of Computer Algorithms. Addison-Wesley,

Reading MA 1974

Buase S. and Van Gelder, A. Computer Algorithms. Addison Wesley Longman, Reading, MA 2000.

Page 1 of 26
 LECTURE NOTE

1. 1 BASIC ALGORITHM ANALYSIS

1.1.1Analysis of Algorithm

It is an analysis which gives the basic information that provides a general idea of how
long an algorithm will take place for a given problem set. Or it simply means an analysis
of resource usage of given algorithms.

1.1.2 Complexity Theory:

The study of the cost of solving interesting problems. Measure the amount of resources
needed to solve the problems. The resources needed are: i. Time ii. Space

1.1.3 Asymptotic Analysis

Worst Case (O) Best case(Ω) Average (𝜃)

Problem
- to Solve

Program in java

P1

A1 A2 A3 A4 A5
Analyse the algorithm in terms of

i. Time ii. Space (memory)

We analyze them or choose the best

1.2 ASYMPTOTIC NOTATION [ O Ω 𝜽]

1.2.1 Big Oh (O)

time (t) Cg(n)
f(n)

Page 2 of 26
 n0 n(input)
If f(n)=3n + 4 g(n) = n

f(n)= Og(n)

f(n) ≤ C g(n) C>0 n≥1

3n+4≤Cn C=4 [or anything >3]

3n+4≤4n
n≥4

1.2.2 Big Omega (Ω)

time (t) f(n)
Cg(n)

n0 n(input)
If f(n)=3n + 4 g(n) = n

f(n)= Ωg(n)

f(n) ≥ C g(n) C>0 n≥1

3n + 4 ≥ Cn C=1 [or anything < 3]

3n + 4 ≥ n

1.2.2 Big Theta (𝜽) C2g(n)

time (t) f(n)
Cg(n)

Page 3 of 26
 n0 n(input)
f(n)= 𝜃 g(n)

C1 g(n) ≤ f(n) ≤ C2 g(n) where C1, C2>0 for n≥ n0 and n0≥1

We have seen that

f(n) ≤ C2 g(n) (Upper bound) of g(n))
3n + 4 ≤ C2n, C2=4 [or anything > 3]
3n + 4 ≥ 4n, n0≥1

Then,

f(n) ≥ C1g(n) C1>0 n≥1 (Lower bound of g(n))

3n + 4 ≥ n, C1=1 for n0≥1

1.2.4.Finding Big Oh (O)

One can find if a function is in O(g) by using the following alternative description:
𝑓(𝑛)
𝑓 ∈ 𝑂(𝑔) lim 𝑔(𝑛) = 𝐶, for some 𝐶 ∈ 𝑅 ∗
𝑛→∞

𝑓(𝑛)
It means that if the limit of 𝑔(𝑛) is some real numbers less than ∞,

f(n)=O(𝑔(𝑛)) .

With some functions, it might not be obvious that is the case. We can then take the derivative of
f and g and apply this same limit.

Example: For each of the following pairs of functions, f(n) and g(n), either f(n)=O(g(n)) or
g(n)=O(f(n)) but not both. Determine which the case is:

i. 𝑓(𝑛) = 𝑛2 + 3𝑛 + 4, 𝑔(𝑛) = 𝑛3 ii. 𝑓(𝑛) = 𝑛 + 𝑙𝑜𝑔𝑛 , 𝑔(𝑛) = √𝑛

1.3 RECURSION (Recursive Algorithms)

Basically there are two types of algorithms which are recursive and non recursive
(iterative). In this section the recursive algorithm will be discuss. Repetition can be achieved by
writing loops, such as for loops and while loops. Another way to achieve repetition is through

Page 4 of 26
recursion. This occurs when a method (function) calls itself. Most modern programming
languages, including java calls itself. Thus recursion is an elegant way of achieving repetitive
tasks.

1.3.1 The Factorial Function

It is a simple way of illustrating recursion. The factorial of a positive integer n, denoted

n! is defined as the product of the integers from 1 to n. If n=0, then n! is given as 1, by
convention. Specifically,

1 𝑖𝑓 𝑛 = 0
𝑛! = {
𝑛. (𝑛 − 1). (𝑛 − 2) … … … … 2.1 𝑖𝑓 𝑛 ≥ 1

Example: 5! =5*4*3*2*1=120. To make connection with methods clearer, n! is denoted as

factorial(n).

The factorial function can be defined in a manner which suggests a recursive formulation.
To see this, observe that

Factorial (5)=5۰(4۰3۰2۰1)=5۰ factorial (4).

Therefore, factorial (5) can be defined in terms of factorial (4). Generally, for a positive integer
n, factorial (n) can be defined as

n۰ factorial (n-1), it leads to the recursive definition as follows;

1 𝑖𝑓 𝑛 = 0
factorial(n) = {
𝑛. 𝑓𝑎𝑐𝑡𝑜𝑟𝑖𝑎𝑙(𝑛 − 1) 𝑖𝑓 𝑛 ≥ 1

The above definition is typical of many recursive definitions. First, it contains one or
more base cases, which are defined non-recursively in terms of fixed quantities. In this case, n=0
is the base case. It also contains one or more recursive cases, which are defined by appealing to
the definition of the function being defined. Observe that there is no circularity in this definition,
because each time the function is invoked. Its argument is smaller by 1.

1.4 Summation

Page 5 of 26
We will be adding up sets of values as analyze algorithms. Therefore, there is a need to use
standard summation formulae.
N N

(i) ∑ c ∗ i = C ∗ ∑ i [𝑊𝑖𝑡ℎ 𝐶 𝑖𝑠 𝑎 𝑐𝑜𝑛𝑠𝑡𝑎𝑛𝑡 𝑒𝑥𝑝𝑟𝑒𝑠𝑠𝑖𝑜𝑛 𝑛𝑜𝑡 𝑑𝑒𝑝𝑒𝑛𝑑𝑒𝑛𝑡 𝑜𝑛 𝑖]

i=1 i=1

N N−C

(ii) ∑ i = ∑(i + C)
i=C i=0

N N C−1

(iii) ∑ i = ∑ i − ∑ i
i=C i=0 i=0

N N N

(iv) ∑(A + B) = ∑ A + ∑ B
i=1 i=1 i=1

N N
It shows that adddin nmbers from N down to 0 is he same as adding
(v) ∑(N − i) = ∑ i [ ]
numbers from 0 up to N
i=1 i=0

(vi) ∑ 1 = N
i=0

(vii) ∑ C = C ∗ N
i=0

N
N(N + 1)
(viii) ∑ i =
2
i=1

The formula (viii) is easy to remember, if one considers pairing up the values. Matching the first
and last, second and second last, and so on gives you a set of values that are all N+1. How many
of these N+1 totals do you get? Well, one gets half of the values one started before pairing them
𝑁 𝑁(𝑁+1)
or 𝑁⁄2. Therefore the result is 2 (𝑁 + 1) = 2

Page 6 of 26
 𝑁
𝑁(𝑁 + 1)(2𝑁 + 1) 2𝑁 3 + 3𝑁 2 + 𝑁
2
(𝑖𝑥) ∑ 𝑖 = =
6 6
𝑖=1

(𝑥) ∑ 2𝑖 = 2𝑁+1 − 1
𝑖=0

𝑁
𝐴𝑁+1 − 1
(𝑥𝑖) ∑ 𝐴𝑖 = , 𝑓𝑜𝑟 𝑠𝑜𝑚𝑒 𝑛𝑢𝑚𝑏𝑒𝑟 𝐴
𝐴−1
𝑖=0

(𝑥𝑖𝑖) ∑ 𝑖2𝑖 = (𝑁 − 1)2𝑁+1 + 2

𝑖=0

𝑁
1
(𝑥𝑖𝑖𝑖) ∑ = 𝑙𝑛𝑁
𝑖
𝑖=0

𝑁
𝑥 − 𝑁𝑥 𝑁 + (𝑁 − 1)𝑥 𝑁+1
(𝑥𝑖𝑣) ∑ 𝑖𝑥 𝑖 =
(1 − 𝑥)2
𝑖=0

Examples: For the following summations, give an equivalent equation without the summation.
𝑁

𝑎) ∑ 𝑖 2 − 2𝑖
𝑖=1

𝑏) ∑ 6𝑖
𝑖=1

𝑐) ∑ 𝑖6𝑖
𝑖=1

2. SEARCHING ALGORITHM

The act of searching for a piece of information in a list is one of the fundamental
algorithms in Computer Science. It is assume that there is a list that contains records of
information, which in practice is stored using an array in a program. The records are assumed to

Page 7 of 26
be in adjacent locations in the list, with no gaps or blank records in the middle. Search algorithm
is the process of looking through a list to find a particular element called target.

The records (lists) will be either unsorted or sorted based on this key value. It simply means, the
unsorted lists are in random order while the sorted lists are in order by increasing key value.

When a list is unsorted, we only have to search sequentially through the list so as to look
the item. It is the simplest of searching algorithm but not very efficient. However, it will
successfully search in any list.

When a list is sorted, the options for searching are expanded to include binary search.
This takes advantage of the ordered nature of the list to eliminate more than one element of the
list with each comparison. It results in a more efficient search.

2.1 Sequential Search

Sequential search looks at elements, one at a time, from the first in the list until a match
for the target is found. It should be obvious that the further down the list a particular key value is,
the longer it will take to find that key value. This is an important fact to remember when we
began to analyze sequential search. The complete algorithm for sequential search is:

SequentialSearch (List, target, N)

List -the elements to be searched
target -the elements being searched for
N -the number of elements in the list
For i=1 to N do
If(target = list[i])
return i
end if
end for
return 0
2.1.1 Worst-Case Analysis of Sequential Search
Sequential search algorithm has two worst cases which are:

 If the target (key) matches the last element in the list.

 If the target is not in the list.

Page 8 of 26
In both cases, whether the target is in the last location or not in the list, this algorithm takes N
comparisons. One will see that this is the upper bound for any search algorithm, because to do
more than N comparisons would mean that the algorithm compared at least one element with the
target at least twice which is unnecessary work, so the algorithm could be improved.

2.1.2 Average-Case Analysis of Sequential Search

There are also two cases of average-case analysis for a search algorithm.

i. It assumes that the search is always successful.

ii. It assumes that the target will sometimes not be found.

i. If the target is in the list, there are N places where that target can be located. It could be in
the first, second, third, fourth and so on locations in the list. It is assume that all of these
1
possibilities are equally likely, giving a probability of 𝑁 for each potential location. This clearly

shows that the number of comparisons is the same as the location where the match occurs. This
gives the following equation for the average case.

1
A(N)=𝑁 ∑𝑁
𝑖=1 𝑖

1 𝑁(𝑁+1)
A(N)=𝑁 * 2

𝑁+1
A(N)= 2

ii. If the target is not in the list, then there are now N+1 possibilities. It is assumed that all
N+1 possibilities are equally likely. As we have stated, in the worst case analysis, there will be N
comparisons if the target is not in the list.

Therefore, the average case analysis when the target is not successful is given by:
1
A(N)= (𝑁+1) ∗ ∑𝑁
𝑖=1 𝑖 + N

1 1
= 𝑁+1 ∑𝑁
𝑖=1 𝑖 + 𝑁+1 ∗ 𝑁

Page 9 of 26
 1 𝑁(𝑁+1) 𝑁
= [𝑁+1 ∗ ] + 𝑁+1
2

𝑁 𝑁
= + 𝑁+1
2

𝑁 𝑁 𝑁 1
=[ 2 + 1] + [𝑁+1 − 1] = [ 2 + 1 − 𝑁+1]

𝑁+2 1
∴A(N)≈ (As N gets very large, 𝑁+1 becomes almost 0.)
2

2.2. Binary Trees

A binary tree is an ordered tree in which every node in the tree has at most two nodes as its
children, and each node has exactly one parent node except the top node which is called the root.

Levels(J) PROPERTIES OF A BINARY TREE Nodes(N)

1 1

2 2

3 4

4 8

i. Each child is labeled as being either left child or right child.

ii. A left child precedes a right child in the ordering of children of a node.
iii. Proper: A binary tree is proper if each node has either zero or two children.

Page 10 of 26
 iv. List: It is a largest binary tree that has N nodes and N levels, that is if each node
has exactly one child.
v. Left Subtree/Right Subtree: The sub-tree rooted at left or right of an internal node.

Mathematical Properties

The number of nodes (N) grows exponentially as we go down the tree. The following are
the mathematical properties relating to the levels number of nodes of a proper binary tree.

1. Number of levels: A binary tree that has N nodes has at least log 2 𝑁 + 1 levels

2. Number of nodes on level K: Considering the root to be on level 1, then the number of
nodes on level k is 2𝑘−1 𝑛𝑜𝑑𝑒𝑠

3. Total number of nodes (leaves): A complete binary tree with J levels (numbered from 1
to J) is one where all leaves in the tree are on level J, and all nodes on levels 1 to J-1 have
exactly two children. Therefore the number of nodes of a tree with J levels is

2𝑗 − 1 𝑛𝑜𝑑𝑒𝑠

2.2.1 Binary Search

Binary search compares the target with the element that is in the middle of an ordered list, we
have three possible results:

i. The target matches the middle element

ii. The target is less than the middle element
iii. The target is greater than the middle element

In (i) the algorithm terminates which is the best case. However, in other two possibilities, we
observe that half of the list will be remove from consideration.

If the target is less than the element at the middle of a sorted list, then the target must be
in the list before the middle element. When the target is greater than the middle element in a
sorted list, then it must be in the list after the element at the middle. This shows that one-half
of the list is eliminated from consideration after one comparison. As the procedure continues,

Page 11 of 26
 we will remove half of what is left of the list with each comparison from consideration. Thus,
the complete algorithm for binary search is

The algorithm of binary search:

BinarySearch( list, target, N )

list the elements to be searched
target the value being searched for
N the number of elements in the list
start = 1
end = N
while start ≤ end do
middle = (start + end) / 2
select (Compare(list[middle], target)) from
case -1:start = middle + 1
case 0:return middle
case 1:end = middle - 1
end select
end while
return 0
In the above algorithm start resets to 1 greater than the middle element that is if the target is
greater than the element at the middle location. Nonetheless, if the target is smaller than the
element at the middle location, then end gets reset to 1 smaller than the element at the middle
location. These are shifted by 1 because we know by three-way comparison that the middle value
is not equal and so can be eliminated from consideration.

2.2.2 Worst-Case Analysis of Binary Search Algorithm

Let the number of elements (nodes) be N = 2k − 1. Then, after 1st pass we have:

i. N = 2k − 1 elements in 1st half

ii. 1 element at the middle
iii. N = 2k − 1 elements in the 2nd half.

Therefore, the next pass will have N = 2k − 1 elements left (for 1 ≤ 𝑗 ≤ 𝑘). This
clearly shows that the last pass of the loop occurs when the list has a size of 1. That is
when k is 1.

Page 12 of 26
 → 21 − 1 = 1. It means there are at most k passes when
N = 2k − 1, The worst case is

K = log 2 (N + 1)

2.2.2 Average Case Analysis of Binary Search Algorithm

There are two situations to be considered when doing an average case analysis

i. The target will always be in the list

ii. The target may not be in the list

In (i), if the target is in the list, there are n possible locations where the target will be found. If we
consider a probability of 1⁄𝑁. Generally, I comparisons are performed in order to search for the

elements that are in the nodes on level i. Also, there are N = 2i−1 nodes on level i, and if N =
2k − 1, there are k levels in the tree. Thus, the average case analysis is

1
A(N) = ∑ki=1 i 2i−1 𝑓𝑜𝑟 N = 2k − 1
N
1
is the probability
N
i denotes the number of comparisons
2i−1 denotes the number of nodes on level i

k
1 1
A(N) = ∗ ∑ i 2i
N 2
i=1
1 1
= ∗ [(k − 1)2k+1 + 2]
N 2
1 1
= ∗ [k2k+1 − 2k+1 + 2]
N 2
1
= [k2k − 2k + 1]
N
[k2k − (2k − 1)]
=
N
k2k
= −1
N
Because N = 2k − 1, and 2k = N + 1
k(N + 1)
A(N) = −1
N
Page 13 of 26
 kN + k
= −1
N
k
=k+ −1
N
k
∴ 𝐴(𝑁) ≈ k − 1 as N gets Larger N becomes 0.
𝐴(𝑁) ≈ k − 1 for 𝑁 = 2𝑘 − 1

Thus, the average case analysis of binary search algorithm when the target is in the list is

𝐴(𝑁) ≈ log 2 (N + 1) − 1

i. The average case analysis of binary search algorithm when the target may not be in
the list is
1 1
𝐴(𝑁) ≈ k − = log 2 (N + 1) −
2 2
Example: 1) Write an algorithm that takes in three distinct integers and determines the largest of
the three.

a) What are the possible input classes that would have to be considered when analyzing this
algorithm?

b) Which one causes the algorithm to do the most comparisons?

c) Which one causes the least?
Solution:

a) Start
get (a, b, c)
least = a
If b < least
least = b
If c < least
least = c
End if
End if
Stop
b)Input classes: there are six input classes; which are: 1 a,b,c 2.a,c,b 3.b,a,c 4.b,c,a 5.c,a,b
6.c,b,a

c) The number of comparison is the same for all the input classes

Example: 2) What is the average complexity of sequential search if there is a 0.25 chance that the
target will not be found in the list and there is a 0.75 chance that when the target is in the list, it
will be found in the first half of the list?

Page 14 of 26
 Solution:

𝑁
2 𝑁
0.75 × 2
= ∗ ∑ 𝑖 + 0 ∗ ∑ 𝑖 + 0.25 × 𝑁
𝑁 𝑁
𝑖=1 𝑖= +1
2

𝑁 𝑁
0.75 +( +1)
2 2
= 𝑁 [ ]+ 0.25N
2
2

𝑁2 𝑁
0.75 +
4 2
= 𝑁 [ ]+ 0.25N
2
2

𝑁2 +2𝑁
0.75 4
= 𝑁 [ ]+ 0.25N
2
2

2∗0.75 𝑁2 +2𝑁 1
= [ ∗ 2]+ 0.25N
𝑁 4

1.5 𝑁2 +2𝑁
=𝑁 [ ]+ 0.25N
8

1.5𝑁+3
= + 0.25N
8

1.5𝑁+3+2𝑁
= 8

3.5𝑁+3
= 8

3. SORTING ALGORITHM

Another class of fundamental computing algorithm will be considered in this section: Sorting
algorithms. Sorting algorithm is one of the techniques use in computing to arrange list of items
either in ascending or descending order. A list of records, which have a special field called the

Page 15 of 26
key, will be discussed. For the purpose of this course, all of the sorting algorithms will sort the
list into increasing order based on this key value. Sorting algorithm includes the following:

1. Bubble sort
2. Insertion sort
3. Shell sort
4. Quick sort

3.1 Bubble Sort: In the bubble sort, each element of the array is compared with the next
element, if these elements are out of ordering then it swaps. When the round of comparisons is
done, the largest value in the array will be place at right most position. In the next round, one
fewer element will be compare (number rounds reduced). The process continues until the last
round in which only two elements need to be compared. In general, the idea behind bubble sort is
to allow smaller values move toward the leftmost position of the list while the larger values
move to the rightmost position.

In details, the algorithm starts each of the passes at the beginning of the list and compares
the elements in location 1 and 2, then the elements in location 2 and 3, then 3 and 4 and so on;
swapping those that are out of order. On the 1st pass, once the algorithm reaches the largest
element, it will be swapped with all of the remaining elements moving it to the end of the list
after the 1st pass. At the 2nd pass the last element of the list will not be considered for sorting.

Below is the algorithm which performs this bubble sort version:

BubbleSort( list, N )

Page 16 of 26
list :the elements to be put into order
N :the number of elements in the list

numberOfPairs = N
swappedElements = true

while swappedElements do
numberOfPairs = numberOfPairs - 1
swappedElements = false
for i = 1 to numberOfPairs do
if list[ i ] > list[ i + 1 ] then
Swap( list[i], list[i + 1] )
swappedElements = true
end if
end for
end while

Example: Show the results of each pass of BubbleSort applied to the list [6, 2, 4, 7, 1, 3, 8, 5]

Solution:
The Original List: 6 2 4 7 1 3 8 5
Pass 1: 2 4 6 1 3 7 5 8
Pass 2: 2 4 1 3 6 5 7 8
Pass 3: 2 1 3 4 5 6 7 8
Pass 4: 1 2 3 4 5 6 7 8
Pass 5: 1 2 3 4 5 6 7 8

3.1.1 Best-Case Analysis of Bubble Sort:

The best case is N-1 comparisons, this happens when the swaps do not occur after the first pass.
That is when the list to be sorted are already arranged in increasing order.

3.1.2 Worst-Case Analysis of Bubble Sort:

The worst case occurs when the data values are in reverse order. In this case, the algorithm does
the largest number of comparisons and swaps. Since we are only interested in counting the
number of comparisons, there are other sets that will lead us to this worst case.

Therefore, the worst case analysis is given as

1 𝑁−1
(𝑁 − 1)𝑁 𝑁 2 − 𝑁
𝑊(𝑁) = ∑ 𝑖 = ∑ 𝑖 = =
2 2
𝑖=𝑁−1 𝑖=1

Page 17 of 26
 1
𝑊(𝑁) ≈ 2 𝑁 2 = 𝑂(𝑁 2 )

3.1.3 Average-Case Analysis of Bubble Sort:

The average case analysis is given by:

1 2
𝐴 (𝑁 ) ≈ 𝑁 = 𝑂(𝑁 2 )
3
3.2 Insertion Sort

The fundamental idea of insertion sort is that, if we have a list that is in sorted order and need to
add a new element, the most efficient way is to place the new element into the correct position
instead of adding it anywhere and then re-sorting the entire list.

It is one of the simplest sorting algorithms which consists of N-1 passes. In this
technique, it ensures that the first element of any list is always a sorted list of size 1. Then, a two-
element sorted list is created by correctly placing the second element of the list into the one-
element list containing the first element. The third element of the list is also inserted into the
two-element sorted list. The process is repeated until all the elements have been put into the
expanding sorted portion of the list. The algorithm that will perform this version of insertion sort
is given below:

InsertionSort( list, N )
list the elements to be put into order
N the number of elements in the list
for i = 2 to N do
newElement = list[ i ]
location = i - 1
while (location 1) and (list[ location ] >
newElement) do
// move any larger elements out of the way
list[ location + 1] = list[ location ]
location = location – 1
end while
list[ location + 1 ] = newElement
end for

Example: Show results of each pass of insertion sort applied to the list [6, 2, 4, 7, 1, 3, 8, 5]

Page 18 of 26
Solution:

The Original List: 6 2 4 7 1 3 8 5

Pass 1: 2 6 4 7 1 3 8 5
Pass 2: 2 4 6 7 1 3 8 5
Pass 3: 2 4 6 7 1 3 8 5
Pass 4: 1 2 4 6 7 3 8 5
Pass 5: 1 2 3 4 6 7 8 5
Pass 6: 1 2 3 4 6 7 8 5
Pass 7: 1 2 3 4 5 6 7 8

3.2.1 Worst-Case Analysis of Insertion Sort

The worst case occurs when the original list is in decreasing order. This causes the algorithm to
the most work since every new element is added to the front of the list. The input set will be
handled as follows. The element at the 2nd location of the list is the first element to be inserted
which is compared to one other at most. The element at location 3 is the 2nd to be inserted which
will be compared to two previous elements. Generally, the ith element inserted will be compared
to I previous elements. This process is repeated for N-1 elements. Thus, the worst-case
complexity for insertion sort is given by:
𝑁−1
(𝑁 − 1)(𝑁) 𝑁 2 − 𝑁
𝑊(𝑁) = ∑ 𝑖 = =
2 2
𝑖=1

𝑊(𝑁) = 𝑂(𝑁 2 )

3.2.2 Worst-Case Analysis of Insertion Sort

The average case-analysis of insertion sort is given by:

𝑁2
𝐴(𝑁) = 4

𝐴(𝑁) = 𝑂(𝑁 2 )

3.3 Shellsort

This algorithm was named after its developer called Donald L. Shell. The shellsort is an
improved version of the straight insertionsort in which diminishing partition are use to sort the
data. It compares elements that are distant apart rather than adjacent. That is the algorithm starts

Page 19 of 26
by comparing elements that are distance apart. So, if there are N elements, then we start with a
value Gap <N.

𝑁
Gap = floor ( 2 ), where N is the number of elements in an array. In each pass, the value
of gap keeps reducing till it reduces the last pass when the gap is 1.

In the last pass shellsort is like insertion sort.

𝑁
Gap = floor ( 2 )

𝑔𝑎𝑝
Gap 1 = floor ( )
2

Example: Show the results of each of the passes of shellsort with the initial list of values [77, 62,
14, 9, 30, 21, 80, 25, 70, 55]

Solution

Original List: 77 62 14 9 30 21 80 25 70 55
𝑁 10
Gap = floor ( 2 ) = ⌊ 2 ⌋ = 5

Pass 1: 77 62 14 9 30 21 80 25 70 55

21 62 14 9 30 77 80 25 70 55

5
Pass 2: Gap = ⌊2⌋ = 2

21 62 14 9 30 77 80 25 70 55

14 9 21 25 30 55 70 62 80 77
2
Pass 3: Gap = ⌊2⌋ = 1

14 9 21 25 30 55 70 62 80 77

9 14 21 25 30 55 62 70 77 80

Page 20 of 26
Example 2 (Class Work): Show the results of each of the passes of shellsort with initial list of
values [6, 2, 4, 7, 1, 3, 8, 5]

4. GRAPH

A graph is an ordered pair G(V,E) of the sets representing the nodes and the edges of the
graph. An edge specifies which vertices have a connection between them.

4.1 Types of Graph

Page 21 of 26
Basically there are three types of graphs which are: undirected graph, directed graph and mixed
graph

4.1.1 Undirected Graph

This is sometimes called graph, has edges that can be traverse in either direction. In this case, an
edge is a set which contains the labels of the nodes that are at the two ends of the edge.

The graph G = ({1,2,3,4,5}, {{1,2}, {1,3}{2,3}{2,4}{3,5}{4,5})

4.1.2 Directed Graph

It is also known as digraph, has edges that can only be traverse in one direction. For a digraph,
our set of edges will have ordered pairs in which the first item is where the edges starts and the
second is where the edges ends.

The directed graph G = ({1, 2, 3, 4, 5}, {(1, 2),(1, 3), (2, 1), (3, 2), (4, 3), (4, 5), (5, 2), (5,4)})

4.1.3 Mixed graph

This is a combination of both directed and undirected graph. This means it has edges of both
directed and undirected graph.

Page 22 of 26
The mixed graph G = ({a,b,c}, {(a,b), (b,c), (c,a)})

4.3 Terminologies

4.3.1 A complete graph

This is a graph with an edge between every pair of nodes. If there are N nodes, there will be
(𝑁 2 −𝑁)
edges in a complete graph without loop edges.
2

2 3

4.3.1 A complete digraph

This is a digraph with an edge allowing traversal between every pair of nodes. Since the edges
allow travel in two directions, whereas as edges of a digraph allow travel in only one direction.
Thus, a complete digraph with N nodes will have twice as many edges. That is (𝑁 2 − 𝑁)
1

2 3

4.3.2 Subgraph
A subgraph (Vs, Es) of a graph or digraph (V, E) is one that has a subset of the vertices (Vs⊆ V)
and edges (Es ⊆ E) of the full graph.

Page 23 of 26
4.3.3 Path
A path between two nodes of a graph or digraph is a sequence of edges that can be travelled
consecutively. In other words, a path between node A and B would begin at A and traverse a set
of edges until node B was reached.

4.3.4 Weighted Graph or digraph

This is a one where each edge has a value called the weight associated with it

4.4 Breadth-First
In a breadth-first traversal, we visit the starting node and then on the first pass visit all the nodes
directly connected to it. In the second pass, we visit nodes that are one more edge away. Because
there might be cycles in the graph, it is possible a node to be on two paths of different lengths
from the starting node, we will not need to consider it again. We will therefore, either need to
keep a list of the nodes we have visited or we will need to use a variable in the node to mark it as
visited to prevent multiple visits. This indicates that the breadth-first is based on a queue.

Example 1: For the digraph below, give the order that the nodes will be first visited when doing
a breadth-first traversal starting at node labeled with A

Solution:
Breadth-first traversal from node A is: A, B,E,F,G,I,C,L,D,H,K,J
Example 2: For the graph below, give the order that the nodes will be first visited when doing a
breadth-first traversal starting at node labeled with 1.

Page 24 of 26
Breadth-first traversal from node 1 is: 2,8,3,7,4,5,6,9

4.5 Depth-First Traversal

In depth-first traversal, we visit the starting node and then proceed to follow links through the
graph until we reach a dead end. In an undirected graph, a node is dead end if all of the nodes
adjacent to it have already been visited. In a directed graph, if a node has no outgoing edges, we
also have a dead end.
When we reach a dead end, we back up along our path until we find an unvisited adjacent
node and then continue in that new direction. The process will have completed when we back up
to the starting node and all the nodes adjacent to it have been visited. In illustrating this
algorithm and all others in this course, if presented with a choice of two nodes, we will choose
the node with the numerically or alphabetically smaller label. From the above explanations, it
shows that the depth-first depended on stack.
Example 1: For the digraph below, give the order that the nodes will be first visited when doing
a depth-first traversal starting at node labeled with A

Depth-first traversal from node A is: A, B,G,C,D,H,L,K,J,F,I,E

Example 2: For the graph below, give the order that the nodes will be first visited when doing a
depth-first traversal starting at node labeled with 1

Page 25 of 26
Depth-first traversal from node 1 is: 1,2,3,4,7,5,6,8,9

Best of Luck!

Page 26 of 26