Tribhuvan University
BSc CSIT 5th Semester
Design and Analysis of Algorithms (CSC325)
Unit 2: Iterative Algorithms
By: Dabbal Singh Mahara
Amrit Campus
1
Iterative Algorithms
• An iterative algorithm is an algorithm that solves a problem by repeating a
set of instructions using loops until a given condition is satisfied.
• It uses four clear cut steps: initialization, condition, execution and
updating.
• It is more efficient in terms of memory utilization and execution speed.
• It is widely used in sorting, searching, and numerical computations due to
its efficiency and simplicity.
2
Factorial of an Integer
• Factorial of any positive integer N is defined to be the product of all integers
between 1 and N inclusive.
• N! = N * (N-1) * (N-2) * … * 3 * 2 * 1
public int factorial (int n)
{
int i, result;
result = 1;
Time Complexity = O(n)
for (i = 1; i <= n; i++)
Space Complexity = O(1)
result = result * i;
return ( result );
}
Greatest Common Divisor (GCD)
• The Greatest Common Divisor (GCD) of two integers is the largest positive
integer that divides both numbers without leaving any remainder.
• For example, GCD of 25 and 135
4
Algorithm for GCD For example, GCD of 25 and 135
Iteration a b r = a mod b
gcd(a, b) { 1 135 25 135 mod 25 = 10
if(a==0) 2 25 10 25 mod 10 = 5
return b
else if(b==0) 3 10 5 10 mod 5 = 0
return a
4 5 0 GCD = 5
else
{
while(b != 0)
{
r =a %b
a=b
b=r
}
return a
}
}
5
Time and Space Complexity
• In each iteration, the algorithm replaces b with a mod b, which is always smaller than b.
• This ensures that the value of the smaller number decreases rapidly, often by at least half
every 1–2 steps.
• Therefore, the number of iterations is proportional to log n, where n = min(a, b),
Time Complexity = O(log n)
• Only a few variables (a, b, r) are used, so the space requirement is constant, i.e., O(1).
6
Fibonacci Sequence
• The Fibonacci sequence is a famous number series where each number is the sum of the two
preceding numbers.
• The Fibonacci sequence starts with: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
Algorithm:
Fibo(n) {
If(n ≤ 0)
Print "Invalid input“
else { • Time Complexity = O(n)
a=0
b=1 • Space Complexity = O(1)
for (i=1;i<=n;i++ )
{
c =a+b
a =b
b=c
}
return c
}
Searching
• Searching is a process of finding an element within the list of elements
stored in any order or randomly.
• Searching is divided into two categories Linear and Binary search.
• Linear search
• Small arrays
• Unsorted arrays
• Binary search
• Large arrays
• Sorted arrays
8
Linear Search
• In linear search, access each element of an array one by one sequentially and see whether it
is desired element or not. A search will be unsuccessful if all the elements are accessed and
the desired element is not found.
• In brief, Simply search for the given element left to right and return the index of the
element, if found. Otherwise return “Not Found”.
Algorithm:
LinearSearch(A, n,key)
{
flag = 0
for(i=0;i<n;i++)
{ • Time complexity = O(n)
if(A[i] == key)
flag = 1 • Space Complexity = O(n)
}
if(flag == 1)
print”Search Successful”
else
print(“Search Unsucessful”)
} 9
Binary Search
• Binary search is an extremely efficient algorithm.
• This search technique searches the given item in minimum possible comparisons.
• To do this binary search, first we need to sort the a elements.
• The logic behind this technique is given below:
i. First find the middle element of the array
ii. Compare the middle element with an item.
iii. There are three cases:
a. If it is a desired element then search is successful
b. If it is less than desired item then search only the first half of the array.
c. If it is greater than the desired element, search in the second half of
the array.
• Repeat the same process until element is found or exhausts in the search area.
• In this algorithm every time we are reducing the search area.
10
Iterative Algorithm
BinarySearch(A, l, r, key)
{
while(l<=r)
{
m = (l + r) /2 ; //integer division
if(key = = A[m]
print " Search successful"
else if (key < A[m])
r=m-1
else
l = m+1
}
if(l>r)
print "unsuccessful search"
}
11
Trace Binary Search
Take input array a[]
2 5 7 9 18 45 53 59 67 72 88 95 101 104
0 1 2 3 4 5 6 7 8 9 10 11 12 13
For Search key = 2
l r mid remarks
0 13 6 Key < a[6] i.e. 2 < 53
0 5 2 Key < a[2] i.e. 2 < 7
0 1 0 Key == a[0] i.e. 2 ==a[0]
Therefore, key found at index 0.
Search Successful !!
Exercise : Trace binary search algorithm for keys:
i. 67
ii. 50
12
iii. 250
Input Array : a[ ]
2 5 7 9 18 45 53 59 67 72 88 95 101 104
0 1 2 3 4 5 6 7 8 9 10 11 12 13
Search for key = 67
l r mid Remarks
0 13 6 Key < a[6] i.e. 67 > 53
7 13 10 Key < a[10] i.e. 67 < 88
7 9 8 Key == a[8] i.e. 67 ==a[8]
Therefore, key found at index 8.
Search Successful !!
13
Given Input Array a[]
2 5 7 9 18 45 53 59 67 72 88 95 101 104
0 1 2 3 4 5 6 7 8 9 10 11 12 13
Search for key = 50
l r mid Remarks
0 13 6 Key < a[6] i.e. 50 < 53
0 5 2 Key < a[2] i.e. 50 > 7
3 5 4 Key > a[4] i.e. 50 >18
5 5 5 Key > a[5] i.e. 50 > 45
6 5 l > r, terminate
Therefore, key not found in the array.
Search Unsuccessful !!
14
Efficiency:
From the above algorithm we can say that the running time of the
algorithm is:
T(n) = T(n/2) + Ο(1)
= Ο(log n)
▪ In the best case output is obtained at one run
i.e. Ο(1) time if the key is at middle.
▪ In the worst case the output is at the end of the array,
So running time is Ο(log n)
▪ In the average case also running time is Ο(log n).
15
The Sorting Problem
• Input: A sequence of n numbers a1, a2, . . . , an
• Output: A permutation (reordering) a1’, a2’, . . . , an’ of the input sequence such that
a1’ ≤ a2’ ≤ · · · ≤ an’
1 2 3 4 5 6
77 42 35 12 101 5
1 2 3 4 5 6
5 12 35 42 77 101
16
Bubble Sort
• The basic idea of this sort is to pass through the array sequentially several
times.
• Each pass consists of comparing each element in the array with its successor
(for example a[i] with a[i + 1]) and interchanging the two elements if they
are not in the proper order.
• After each pass an element is placed in its proper place and is not considered
in succeeding passes.
17
"Bubbling Up" the Largest Element
• Traverse a collection of elements
• Move from the front to the end
• “Bubble” the largest value to the end using pair-wise comparisons and swapping
1 2 3 4 5 6
77 42 35 12 101 5
18
“Bubbling Up” the Largest Element
• Traverse a collection of elements
• Move from the front to the end
• “Bubble” the largest value to the end using pair-wise comparisons and swapping
1 2 3 4 5 6
7742 Swap4277 35 12 101 5
19
“Bubbling Up” the Largest Element
• Traverse a collection of elements
• Move from the front to the end
• “Bubble” the largest value to the end using pair-wise comparisons and swapping
1 2 3 4 5 6
42 7735 Swap 3577 12 101 5
20
“Bubbling Up” the Largest Element
• Traverse a collection of elements
• Move from the front to the end
• “Bubble” the largest value to the end using pair-wise comparisons and swapping
1 2 3 4 5 6
42 35 7712 Swap 12
77 101 5
21
“Bubbling Up” the Largest Element
• Traverse a collection of elements
• Move from the front to the end
• “Bubble” the largest value to the end using pair-wise comparisons and swapping
1 2 3 4 5 6
42 35 12 77 101 5
No need to swap
22
“Bubbling Up” the Largest Element
• Traverse a collection of elements
• Move from the front to the end
• “Bubble” the largest value to the end using pair-wise comparisons and swapping
1 2 3 4 5 6
42 35 12 77 1015 Swap 101
5
23
“Bubbling Up” the Largest Element
• Traverse a collection of elements
• Move from the front to the end
• “Bubble” the largest value to the end using pair-wise comparisons and swapping
1 2 3 4 5 6
42 35 12 77 5 101
Largest value correctly placed
24
Items of Interest
• Notice that only the largest value is correctly placed
• All other values are still out of order
• So we need to repeat this process
1 2 3 4 5 6
42 35 12 77 5 101
Largest value correctly placed
25
Repeat “Bubble Up” How Many Times?
• If we have N elements…
• And if each time we bubble an element, we place it in its correct
location…
• Then we repeat the “bubble up” process N – 1 times.
• This guarantees we’ll correctly place all N elements.
26
“Bubbling” All the Elements
1 2 3 4 5 6
42 35 12 77 5 101
1 2 3 4 5 6
35 12 42 5 77 101
1 2 3 4 5 6
N-1
12 35 5 42 77 101
1 2 3 4 5 6
12 5 35 42 77 101
1 2 3 4 5 6
5 12 35 42 77 101
27
Reducing the Number of Comparisons
1 2 3 4 5 6
77 42 35 12 101 5
1 2 3 4 5 6
42 35 12 77 5 101
1 2 3 4 5 6
35 12 42 5 77 101
1 2 3 4 5 6
12 35 5 42 77 101
1 2 3 4 5 6
12 5 35 42 77 101
28
Algorithm
BubbleSort(A, n)
{
for(i = 0; i <n-1; i++)
{
for(j = 0; j < n-i-1; j++)
{
if(A[j] > A[j+1])
{
temp = A[j];
A[j] = A[j+1];
A[j+1] = temp;
}
}
}
}
29
Time Complexity:
Inner loop executes for (n-1) times when i=0, (n-2) times when i=1 and so on:
Time complexity = (n-1) + (n-2) + (n-3) + …………………………. +2 +1
= O(n2)
Space Complexity:
Since no extra space besides 3 variables is needed for sorting
Space complexity = O(n)
30
Selection Sort
• Idea:
Find the least (or greatest) value in the array, swap it into the leftmost(or rightmost)component
(where it belongs), and then forget the leftmost component. Do this repeatedly.
• Let a[n] be a linear array of n elements. The selection sort works as follows:
• pass 1: Find the location loc of the maximum element in the list of n elements a[0], a[1],
a[2], a[3], …......,a[n-1] and then interchange a[loc] and a[n-1].
• Pass 2: Find the location loc of the max element in the sub-list of n-1 elements a[0], a[1],
a[2], a[3], …......, a[n-2] and then interchange a[loc] and a[n-2].
• Continue in the same way. Finally, we will get the sorted list
a[0] <= a[1] <= a[2] <= a[3] <= ..... <= a[n-1].
31
Example:
Consider the array: 15, 10, 20, 25, 5
After Pass 1: 5, 10, 20, 25, 15
After Pass 2: 5, 10, 20, 25, 15
After Pass 3: 5, 10, 15, 25, 20
After Pass 4: 5, 10, 15, 20, 25
32
Algorithm:
SelectionSort( A, n )
{
for( i = 0;i < n-1 ;i++)
{
min =A[i];
minloc=i;
for ( j = i + 1;j < n ;j++)
{
if (A[j] < min)
{
min = A[j];
minloc=j;
}
}
if(i!=loc)
swap(A[i],A[minloc]);
}
}
33
Time Complexity:
• Inner loop executes for (n-1) times when i=0, (n-2) times when i=1 and so on:
Time complexity T(n) = (n-1) + (n-2) + (n-3) + …………………………. +2 +1
= O(n2)
• The complexity of this algorithm is same as that of bubble sort, but number of swap
operations is reduced greatly.
Space Complexity:
Since no extra space besides 5 variables is needed for sorting,
Space complexity = O(n)
34
Insertion Sort
Idea: like sorting a hand of playing cards start with an empty left hand and the cards facing
down on the table. Remove one card at a time from the table, Compare it with each of the cards
already in the hand, from right to left and insert it into the correct position in the left hand. The
cards held in the left hand are sorted.
Suppose an array a[n] with n elements. The insertion sort works as follows:
pass 1: a[0] by itself is trivially sorted.
Pass 2: a[1] is inserted either before or after a[0] so that a[0], a[1] is sorted.
Pass 3: a[2] is inserted into its proper place in a[0],a[1] that is before a[0], between a[0]
and a[1], or after a[1] so that a[0],a[1],a[2] is sorted.
.......................................
pass N: a[n-1] is inserted into its proper place in a[0],a[1],a[2],........,a[n-2] so that
a[0],a[1],a[2],............,a[n-1] is sorted with n elements.
35
Example:
36
Algorithm:
InsertionSort(A, n)
{
for( i = 1;i < n ;i++)
{
temp = A[i]
for ( j = i -1; j >=0 and A[j] > temp; j--)
{
A[j+1] = A[j];
}
A[j+1] = temp;
}
}
37
Complexity
• Best case:
If array elements are already sorted, inner loop executes only 1 time for i=1,2,3,… , n-1 for
each. So, total time complexity = 1+1+1+ …………..+1 (n-1) times = n-1 = O(n)
• Worst Case:
Time complexity T(n) = 1 + 2 + 3 + ⋯ + (n−1) = n(n−1)/2
⇒ 𝑇 𝑛 = 𝑂 𝑛2
• Space Complexity:
Since no extra space besides 3variables is needed for sorting,
Space complexity = O(n)
38
Thank You!
39