[go: up one dir, main page]

0% found this document useful (0 votes)
32 views39 pages

Data Structures and Algorithms

The document discusses various searching techniques for data structures including sequential, binary, and Fibonacci searches. It provides details on each technique such as complexity analyses and coding examples for linear search. Key searching algorithms and their applications are explained.

Uploaded by

Simbiso
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
32 views39 pages

Data Structures and Algorithms

The document discusses various searching techniques for data structures including sequential, binary, and Fibonacci searches. It provides details on each technique such as complexity analyses and coding examples for linear search. Key searching algorithms and their applications are explained.

Uploaded by

Simbiso
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 39

MIDLANDS S T A T E UNIVERSITY

FACULTY OF COMMERCE

GROUP 1 ASSIGNMENT

Boriwondo Valerie Chigama Tinashe Blessing

Chihaka Vimbai Katsande Joe

Malvern Masiye Makwasha Prisca Rumbidzai

Mandizvo Mazvitashe Manowa Walter

Mhandu Tinashe Vudzijena Rodia Simbiso

Chikambure Junic Richard Mukechiwa

Jo-Anne Macharavanda

PROGRAMME: HOUNORS IN INFORMATION SYSTEMS

MODULE: DATA STRUCTURES AND ALGORITHMS

LEVEL 1 SEMESTER 2

LECTURER: MR GAVAI

DUE DATE: 25 JUNE 2021


SEARCHING TECHNIQUES DATA STRUCTURE AND ANALYSIS

• Searching is an operation or a technique that helps finds the place of a given element
or value in the list.
• Any search is said to be successful or unsuccessful depending upon whether the
element that is being searched is found or not.
• Searching is the process of finding a given value position in a list of values.
• It decides whether a search key is present in the data or not.
• It is the algorithmic process of finding a particular item in a collection of items.

It can be done on internal data structure or on external data structure

Data Structure - Search Techniques

• Searching in data-structure refers to the process of finding a desired element in set of


items. The desired element is called "target". The set of items to be searched in, can
be any data-structure like − list, array, linked-list, tree or graph.
• Search refers to locating a desired element of specified properties in a collection of
items. We are going to start our discussion using following commonly used and
simple search algorithms.

Searching Techniques in data structure and analysis are as below:

• Sequential Search

• Binary Search

• Fibonnaci search

• Comparison of sorting algorithms

• BFS & DFS

• Analysis of the techniques


Sequential Search

Sequential search is made over all items one by one. Every item is checked and if a match is
found then that particular item is returned, otherwise the search continues till the end of the
data structure. We often do this in your daily life, say when you are looking through your
shopping list to cross out an item you have picked up.

Linear search is a method of finding elements within a list. It is also called a sequential
search. It is the simplest searching algorithm because it searches the desired element in a
sequential manner.

It compares each and every element with the value that we are searching for. If both are
matched, the element is found, and the algorithm returns the key's index position.

For example: Searching for the number 1 in the array below.

The search begins at index 0 and compares the element at index 0 to the search criteria, in
this case 1. Does 2 = 1? No. This process of comparison continues until the value and index 2
are compared. Does 1 = 1? Yes. The algorithm can continue and search for other instances
until the end of the array, or stop the search.

Index [0] [1] [2] [3] [4]

Data 2 5 1 3 4

for i = 0 to 4

if Numbers[i] == 1 then
print("Item found")

stop

next i

Concept of Linear/Sequential Search

Let's understand the following steps to find the element key = 7 in the given list.

Step - 1: Start the search from the first element and Check key = 7 with each element of list
x.

Step - 2: If element is found, return the index position of the key.


Step - 3: If element is not found, return element is not present.

Linear Search Algorithm

There is list of n elements and key value to be searched.

Below is the linear search algorithm.

1. LinearSearch(list, key)
2. for each item in the list
3. if item == value
4. return its index position
5. return -1

Explanation

In the above code, we have created a function linear_Search(), which takes three arguments
- list1, length of the list, and number to search. We defined for loop and iterate each element
and compare to the key value. If element is found, return the index else return -1 which
means element is not present in the list.

Linear Search Complexity

Time complexity of linear search algorithm -

o Base Case - O(1)

o Average Case - O(n)

o Worst Case -O(n)


Linear search algorithm is suitable for smaller list (<100) because it check every element to
get the desired number. Suppose there are 10,000 element list and desired element is
available at the last position, this will consume much time by comparing with each element of
the list.

In linear search, best-case complexity is O(1) where the element is found at the first index.
Worst-case complexity is O(n) where the element is found at the last index or element is not
present in the array.

Advantages of a linear search

 Will perform fast searches of small to medium lists. With today's powerful computers,
small to medium arrays can be searched relatively quickly.

 The list does not need to sorted. Unlike a binary search, linear searching does not require
an ordered list.

 Not affected by insertions and deletions. As the linear search does not require the list to
be sorted, additional elements can be added and deleted. As other searching algorithms
may have to reorder the list after insertions or deletions, this may sometimes mean a linear
search will be more efficient.

Disadvantages of a linear search

 Slow searching of large lists. For example, when searching through a database of
everyone in the Northern Ireland to find a particular name, it might be necessary to search
through 1.8 million names before you found the one you wanted. This speed disadvantage
is why other search methods have been developed.
Benefits and Drawbacks

The benefit is that it is a very simple search and easy to program. In the best-case scenario,
the item you are searching for may be at the start of the list in which case you get it on the
very first try.

Its drawback is that if your list is large, it may take a while to go through the list. In the
worst-case scenario, the item you are searching for may not be in the list, or it may be at the
opposite end of the list.

Coding a Linear Search

Let's first develop an algorithm for performing a linear search. We will then convert this into
a Python script.

 Let's start with a list of numbers, say 10 of them


 First, we will ask for a number we think may be in the list. We will call this variable
''searchItem''
 Also, we will set a flag variable called ''found'' to false
 Now loop thru the entire list from start to end
o Compare the item at the current position in the list with ''searchItem''
o If it matches, then set ''found'' to true and exit the loop, or else, move on to the
next position
 Otherwise, if we have searched the entire list, ''searchItem'' was not found, so ''found''
remains false

Here's the code in python using the algorithm above.

1. nlist = [4, 2, 7, 5, 12, 54, 21, 64, 12, 32]


2. print('List has the items: ', nlist)
3. searchItem = int(input('Enter a number to search for: '))
4. found = False
5. for i in range(len(nlist)):
6. if nlist[i] == searchItem:
7. found = True
8. print(searchItem, ' was found in the list at index ', i)
9. break
10. if found == False:
11. print(searchItem, ' was not found in the list!')

BINARY SEARCH

• A binary search is an advanced type of search algorithm that finds and fetches data
from a sorted list of items.

• Its core working principle involves dividing the data in the list to half until the
required value is located and displayed to the user in the search result.

• This search algorithm works on the principle of divide and conquer in which the list is
divided into two halves and the item is compared with the middle element of the list.
If the match is found then, the location of middle element is returned otherwise, we
search into either of the halves depending upon the result produced through the match.
.

• It can be known as half-interval search, logarithmic search or binary chop.

• It's time complexity of O(log n) makes it very fast as compared to other sorting
algorithms.

Points to note when using binary search

• If the desired value is equal to the central index’s worth, then the index is returned as
an answer.

• If the target value is lower than the central index’s deal of the list, then the list’s right
side is ignored.

• If the desired value is greater than the central index’s value, then the left half is
discarded.

The process is then repeated on shorted lists until the target value is found.

Consider-

• There is a linear array ‘a’ of size ‘n’.

• Binary search algorithm is being used to search an element ‘item’ in this linear array.

• If search ends in success, it sets loc to the index of the element otherwise it sets loc to
-1.

• Variables beg and end keeps track of the index of the first and last element of the
array or sub array in which the element is being searched at that instant.

• Variable mid keeps track of the index of the middle element of that array or sub array
in which the element is being searched at that instant.

Algorithm Example

Begin

Set beg = 0
Set end = n-1

Set mid = (beg + end) / 2

while ( (beg <= end) and (a[mid] ≠ item) ) do

if (item < a[mid]) then

Set end = mid - 1

else

Set beg = mid + 1

endif

Set mid = (beg + end) / 2

endwhile

if (beg > end) then

Set loc = -1

else

Set loc = mid

endif

End

• Binary Search Algorithm searches an element by comparing it with the middle most
element of the array.

Then, following three cases are possible-

1. If the element being searched is found to be the middle most element, its index is
returned.

2. If the element being searched is found to be greater than the middle most element,
then its search is further continued in the right sub array of the middle most element.
3. If the element being searched is found to be smaller than the middle most element,
then its search is further continued in the left sub array of the middle most element.

This iteration keeps on repeating on the sub arrays until the desired element is found or size
of the sub array reduces to zero

• We are given the following sorted linear array.

• Element 15 has to be searched in it using Binary Search Algorithm.

Step-1:

• To begin with, we take beg=0 and end=6.


• We compute location of the middle element as-
mid
= (beg + end) / 2

Step-2:

• Since a[mid] = 20 > 15, so we take end = mid – 1 = 3 – 1 = 2 whereas beg remains
unchanged.

• We compute location of the middle element as-

mid

= (beg + end) / 2
= (0 + 2) / 2

=1

• Here, a[mid] = a[1] = 10 ≠ 15 and beg < end.

• So, we start next iteration.

Step-3:

• Since a[mid] = 10 < 15, so we take beg = mid + 1 = 1 + 1 = 2 whereas end remains
unchanged.

• We compute location of the middle element as-

mid

= (beg + end) / 2

= (2 + 2) / 2

=2

• Here, a[mid] = a[2] = 15 which matches to the element being searched.

• So, our search terminates in success and index 2 is returned.

Advantages and Disadvantages of binary search algorithm

Advantages Disadvantages
• It eliminates half of the list from • It employs recursive approach which
further searching by using the result requires more stack space.
of each comparison.
• Programming binary search
• This information is used to narrow algorithm is error prone and
the search. difficult.

• For large lists of data, it works • The interaction of binary search with
significantly better than linear memory hierarchy i.e. caching is
search. poor.
(because of its random access nature)

Time Complexity Analysis

Binary Search time complexity analysis is done below-

• In each iteration or in each recursive call, the search gets reduced to half of the array.

• So for n elements in the array, there are log2n iterations or recursive calls.

• Thus, Time Complexity of Binary Search Algorithm is O(log2n).

• Here, n is the number of elements in the sorted linear array.

This time complexity of binary search remains unchanged irrespective of the element position
even if it is not present in the array

Fibonacci search

• Fibonacci search is used to search an element of a sorted array with the help of
Fibonacci numbers. It studies the locations whose addresses have lower dispersion.

• Fibonacci number is subtracted from the index thereby reducing the size of the list.
• The Fibonacci search technique is a method for searching a sorted array using a divide
and conquer algorithm that uses Fibonacci numbers to narrow down possible
locations.

• Fibonacci search divides the sorted array into two sections of sizes that are
consecutive Fibonacci numbers, as opposed to binary search, which divides the array
into two equal-sized parts, one of which is analyzed further

• Fibonacci Search is a comparison-based technique that uses Fibonacci numbers to


search an element in a sorted array:

• Works for sorted arrays

• A Divide and Conquer Algorithm.

• Has Log n time complexity.

Fibonacci Numbers

• Fibonacci Numbers are recursively defined as F(n) = F(n-1) + F(n-2), F(0) = 0, F(1) =
1.

• First few Fibonacci Numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …


Key points about Fibonacci search are:

• Fibonacci Search examines closer elements in few steps. So when input array is big
that cannot fit in CPU cache or in RAM, it is useful.

• On average, fibonacci search requires 4% more comparisons than binary search

• Fibonacci search requires only addition and subtraction whereas binary search
requires bit-shift, division or multiplication operations.

• Fibonacci search can reduce the time needed to access an element in a random access
memory.

• On magnetic tape where seek time depends on the current head position, there are two
considerations: longer seek time and more comparisons that leads to prefer Fibonacci
search

Advantages of Fibonacci Search

 When the element being searched for has a non-uniform access storage

 Can be used in magnetic tapes

 Can be used for large arrays which do not fit in the CPU cache or in the RAM

Differences with Binary Search:

 Fibonacci Search divides given array in unequal parts

 Binary Search uses the division operator to divide range. Fibonacci Search doesn’t
use /, but uses + and -. The division operator may be costly on some CPUs.

 Fibonacci Search examines relatively closer elements in subsequent steps. So when


the input array is big that cannot fit in CPU cache or even in RAM, Fibonacci Search
can be useful.

Fibonacci Search Algorithm


/* Returns index of x if present, else returns -1 */
int fibonaccianSearch(int arr[], int x, int n)
{
/* Initialize fibonacci numbers */
int fbM2 = 0; // (m-2)'th Fibonacci number
int fbM1 = 1; // (m-1)'th Fibonacci number
int fbM = fbM2 + fbM1; // m'th Fibonacci
// Marks the eliminated range from front
int offset = -1;
/* fbM is going to store the smallest Fibonacci
number greater than or equal to n */
while (fbM < n)
{
fbM2 = fbM1;
fbM1 = fbM;
fbM = fbM2 + fbM1;
}

Fibonacci Search Algorithm

/* while there are elements to be inspected. Note that


we compare arr[fbM2] with x. When fbM becomes 1,
fbMm2 becomes 0 */
while (fbM > 1)
{
// Check if fbMm2 is a valid location
int i = min(offset+fbM2, n-1);

/* If x is greater than the value at index fbMm2,


cut the subarray array from offset to i */
if (arr[i] < x)
{
fbM = fbM1;
fbM1 = fbM2;
fbM2 = fbM - fbM1;
offset = i;
}
/* If x is greater than the value at index fbMm2,
cut the subarray after i+1 */
else if (arr[i] > x)
{
fbM = fbM2;
fbM1 = fbM1 - fbM2;
fbM2 = fbM - fbM1;
}

/* element found. return index */


else return i;
}

/* comparing the last element with x */


if(fbM1 && arr[offset+1]==x)
return offset+1;

/*element not found. return -1 */


return -1;
Fibonacci Search Example

 Let’s define a function to generate a Fibonacci number at the index of n


def FibonacciGenerator(n):
if n < 1:
return 0
elif n == 1:
return 1
else:
return FibonacciGenerator(n - 1) + FibonacciGenerator(n - 2)

 Let’s consider the following array and the number to be searched

arr = [10, 22, 30, 44, 56, 58, 60, 70, 100, 110, 130]
x = 60

 Now, let’s define a function that will divide the list and search for the number as per
the Fibonacci Search

def FibonacciSearch(arr, x):


m=0
while FibonacciGenerator(m) < len(arr): #
m=m+1
offset = -1
while (FibonacciGenerator(m) > 1):
i = min( offset + FibonacciGenerator(m - 2),len(arr) - 1)
print('Current Element : ',arr[i])
if (x > arr[i]):
m=m-1
offset = i
elif (x < arr[i]):
m=m-2
else:
return i
 Now, let’s define a function that will divide the list and search for the number as per
the Fibonacci Search

if(FibonacciGenerator(m - 1) and arr[offset + 1] == x):


return offset + 1
return -1print('Number found at index : ',FibonacciSearch(arr, x))

Fibonacci Search Algorithm Complexity

 Worst case time complexity: Θ(logn)

 Average case time complexity: Θ(log n)

 Best case time complexity: Θ(1) - occurs when the element to be searched is
the first element we compare.

 Space complexity: Θ(1) -because no extra space other than temporary


variables is required.

With each step, the search space is reduced by 1/3 on average, hence, the time complexity is
O(log n) where the base of the logarithm is 3.

What is the time complexity of Fibonacci Search?

A) O(logn) -Explanation: In the case of large arrays, it is better than binary search since it
splits the array into two bits, but they are not identical. Its time complexity is O(logn).

Fibonacci Search Algorithm Implementation in Python

 First, we need to have the length of the given list. Then we find the smallest Fibonacci
number greater than or equal to the size of the list. That means if the size of the list is
100, then the smallest Fibonacci number greater than 100 is 144. Let us say that this is
the nth Fibonacci number. In the above example, 144 is the 12th Fibonacci number.

 After this, we move back twice in the Fibonacci series from that number. Essentially,
we find the (n-2)th Fibonacci number.
 Now let us dive into the code for this algorithm:

Fibonacci Search Algorithm Implementation in Python

def fibonacci_search(lst, target):

size = len(lst)

start = -1

f0 = 0

f1 = 1

f2 = 1

while(f2 < size):

f0 = f1

f1 = f2

f2 = f1 + f0

while(f2 > 1):

index = min(start + f0, size - 1)

if lst[index] < target:

f2 = f1

f1 = f0

f0 = f2 - f1

elif lst[index] > target:

f2 = f0

f1 = f1 - f0

f0 = f2 - f1

else:

return index
if (f1) and (lst[size - 1] == target):

return size - 1

return None

What is Sorting Algorithm?

Sorting algorithm is an algorithm that puts elements of a list in a certain order. The most
frequently used orders are numerical order and lexicographical order.
Efficient sorting is important for optimizing the efficiency of other algorithms which require
input data to be in sorted lists.

List of mostly used Sorting Algorithms

Basic Sorting Algorithms:

1. Bubble Sort

2. Selection Sort

3. Insertion Sort

4. Heap Sort

5. Merge Sort

6. Quick Sort

BFS and DFS

Graph definitions

A graph G = (V, E) consists of a set of vertices, V, and a set of edges, E, where each edge is a
pair (v,w) s.t. v,w  V.Vertices are sometimes called nodes, edges are sometimes called
arcs.If the edge pair is ordered then the graph is called a directed graph (also called digraphs)
We also call a normal graph (which is not a directed graph) an undirected graph.When we
say graph we mean that it is an undirected graph.Two vertices of a graph are adjacent if they
are joined by an edge.Vertex w is adjacent to v iff (v,w)  E.In an undirected graph with
edge (v, w) and hence (w,v) w is adjacent to v and v is adjacent to w.

A path between two vertices is a sequence of edges that begins at one vertex and ends at
another vertex.i.e. w1, w2, …, wN is a path if (wi, wi+1)  E for 1  i . N-1

• A simple path passes through a vertex only once.

• A cycle is a path that begins and ends at the same vertex.

• A simple cycle is a cycle that does not pass through other vertices more than once.

A connected graph has a path between each pair of distinct vertices. A complete graph has
an edge between each pair of distinct vertices. A complete graph is also a connected graph.
But a connected graph may not be a complete graph.

Graph Traversal

Graph traversal means visiting every vertex and edge exactly once in a well-defined order.
While using certain graph algorithms, you must ensure that each vertex of the graph is visited
exactly once. The order in which the vertices are visited are important and may depend upon
the algorithm or question that you are solving.

During a traversal, it is important that you track which vertices have been visited. The most
common way of tracking vertices is to mark them.
A graph-traversal algorithm starts from a vertex v, visits all of the vertices that can be
reachable from the vertex v. A graph-traversal algorithm visits all vertices if and only if the
graph is connected. A connected component is the subset of vertices visited during a traversal
algorithm that begins at a given vertex. A graph-traversal algorithm must mark each vertex
during a visit and must never visit a vertex more than once. Thus, if a graph contains a cycle,
the graph-traversal algorithm can avoid infinite loop.

We look at two graph-traversal algorithms: Depth-First Search and Breadth-First Search.


Many problems require processing all graph vertices (and edges) in systematic fashion

Graph traversal algorithms:

– Depth-first search (DFS)

– Breadth-first search (BFS)

Depth first search

 Depth first Search or Depth first traversal is a recursive algorithm for searching all the
vertices of a graph or tree data structure. Traversal means visiting all the nodes of
a graph. Unlike trees, graphs may contain cycles
 It uses the concept of backtracking. It involves thorough searches of all the nodes by
going ahead if potential, else by backtracking.
 Here, the word backtrack means once you are moving forward and there are not any
more nodes along the present path, you progress backward on an equivalent path to
seek out nodes to traverse. All the nodes are progressing to be visited on the current
path until all the unvisited nodes are traversed after which subsequent paths are going
to be selected

Depth First Search Algorithm

A standard DFS implementation puts each vertex of the graph into one of two categories:

1. Visited

2. Not Visited

The purpose of the algorithm is to mark each vertex as visited while avoiding cycles.

The DFS algorithm works as follows:


1. Start by putting any one of the graph's vertices on top of a stack.

2. Take the top item of the stack and add it to the visited list.

3. Create a list of that vertex's adjacent nodes. Add the ones which aren't in the visited
list to the top of the stack.

4. Keep repeating steps 2 and 3 until the stack is empty.

Depth First Search Example

Let's see how the Depth First Search algorithm works with an example. We use an undirected
graph with 5 vertices.

Undirected graph with 5 vertices

We start from vertex 0, the DFS algorithm starts by putting it in the Visited list and putting
all its adjacent vertices in the stack.

Visit the element and put it in the visited list


Next, we visit the element at the top of stack i.e. 1 and go to its adjacent nodes. Since 0 has
already been visited, we visit 2 instead.

Visit the element at the top of stack

Vertex 2 has an unvisited adjacent vertex in 4, so we add that to the top of the stack and visit
it.

Vertex 2 has an unvisited adjacent vertex in 4, so we add that to the top of the stack and visit
it.

After we visit the last element 3, it doesn't have any unvisited adjacent nodes, so we have
completed the Depth First Traversal of the graph.
DFS Implementation (Source Code)

# Using a Python dictionary to act as an adjacency list

graph = {

'5': ['3','7'],

'3': ['2', '4'],

'7': ['8'],

'2': [],

'4’: ['8'],

'8’: []

visited = set () # Set to keep track of visited nodes of graph.


def dfs (visited, graph, node): #function for dfs

if node not in visited: O (1)

print (node)

visited. Add (node) O(1)

for neighbour in graph[node]: k

dfs (visited, graph, neighbour)

# Driver Code

print("Following is the Depth-First Search")

dfs(visited, graph, '5')

In the code, first, we will create the graph for which we will use the depth-first search. After
creation, we will create a set for storing the value of the visited nodes to keep track of the
visited nodes of the graph.

After the above process, we will declare a function with the parameters as visited nodes, the
graph itself and the node respectively. And inside the function, we will check whether any
node of the graph is visited or not using the “if” condition. If not, then we will print the node
and add it to the visited set of nodes.

Then we will go to the neighboring node of the graph and again call the DFS function to use
the neighbor parameter.

At last, we will run the driver code which prints the final result of DFS by calling the DFS the
first time with the starting vertex of the graph.

Output

The output of the above code is as follow:

Following is the Depth-First Search


532487
Time Complexity of DFS = O(V+E)

V- the number of nodes

E- the number of edges

Space Complexity of the algorithm is O(V)

Applications of Depth First Search

Depth-first search (DFS) is an algorithm (or technique) for traversing a graph.

Following are the problems that use DFS as a building block.

1) For an unweighted graph, DFS traversal of the graph produces the minimum spanning tree
and all pair shortest path tree.

2) Detecting cycle in a graph A graph has cycle if and only if we see a back edge during
DFS. So we can run DFS for the graph and check for back edges.

3) Path Finding We can specialize the DFS algorithm to find a path between two given
vertices u and z.

i) Call DFS(G, u) with u as the start vertex.

ii) Use a stack S to keep track of the path between the start vertex and the current vertex.

iii) As soon as destination vertex z is encountered, return the path as the contents of the stack

4) Finding Strongly Connected Components of a graph A directed graph is called strongly


connected if there is a path from each vertex in the graph to every other vertex.

Breadth First Search

• Visits graph vertices by moving across to all the neighbors of last visited vertex

• Instead of a stack, BFS uses a queue

• Similar to level-by-level tree traversal

• “Redraws” graph in tree-like fashion (with tree edges and cross edges for undirected
graph)
• After visiting a given vertex v, the breadth-first traversal algorithm visits every vertex
adjacent to v that it can before visiting any other vertex.

The breath-first traversal algorithm does not completely specify the order in which it should
visit the vertices adjacent to v.We may visit the vertices adjacent to v in sorted order.BFS has
same efficiency as DFS and can be implemented with graphs represented as:

• adjacency matrices: Θ(V2)

• adjacency lists: Θ(|V|+|E|)

• Yields single ordering of vertices (order added/deleted from queue is the same)

Algorithm for Breadth First Search


• Applications: same as DFS, but can also find paths from a vertex to all other vertices with
the smallest number of edges

BASIS FOR COMPARISON BFS DFS


Basic Vertex-based algorithm Edge-based algorithm
Data structure used to store the Queue Stack
nodes
Memory consumption Inefficient Efficient
Structure of the constructed tree Wide and short Narrow and long
Traversing fashion Oldest unvisited vertices are Vertices along the edge are
explored at first. explored in the beginning.
Optimality Optimal for finding the shortest Not optimal
distance, not in cost.
Application Examines bipartite graph, Examines two-edge connected
connected component and graph, strongly connected
shortest path present in a graph. graph, acyclic graph and
topological order.
Analysis of Algorithm techniques

Searching Algorithm Time Complexity Space Complexity

Best Average Worst


Case Case Case

Linear / Sequential O(1) O(n) O(n) O(1)

Binary O(1) O(logn) O(logn) iterative implementation


O(1)

recursive implementation
O(logn)

Fibonacci O(1) O(logn) O(logn) O(1)

Why Analyze an Algorithm?

 The most straightforward reason for analyzing an algorithm is to discover its


characteristics in order to evaluate its suitability for various applications or compare it
with other algorithms for the same application. Moreover, the analysis of an algorithm
can help us understand it better, and can suggest informed improvements. Algorithms
tend to become shorter, simpler, and more elegant during the analysis process.

 A complete analysis of the running time of an algorithm involves the following steps:

 Implement the algorithm completely.

 Determine the time required for each basic operation.

 Identify unknown quantities that can be used to describe the frequency of execution of
the basic operations.

 Develop a realistic model for the input to the program.


 Analyze the unknown quantities, assuming the modelled input.

 Calculate the total running time by multiplying the time by the frequency for each
operation, then adding all the products.

 In theoretical analysis of algorithms, it is common to estimate their complexity in the


asymptotic sense, i.e., to estimate the complexity function for arbitrarily large input.
The term "analysis of algorithms" was coined by Donald Knuth.

 Algorithm analysis is an important part of computational complexity theory, which


provides theoretical estimation for the required resources of an algorithm to solve a
specific computational problem. Most algorithms are designed to work with inputs of
arbitrary length. Analysis of algorithms is the determination of the amount of time and
space resources required to execute it.

 Usually, the efficiency or running time of an algorithm is stated as a function relating


the input length to the number of steps, known as time complexity, or volume of
memory, known as space complexity.

 Analysis of algorithm is the process of analysing the problem-solving capability of the


algorithm in terms of the time and size required (the size of memory for storage while
implementation). However, the main concern of analysis of algorithms is the required
time or performance.

Generally, we perform the following types of analysis −

 Worst-case − The maximum number of steps taken on any instance of size a.

 Best-case − The minimum number of steps taken on any instance of size a.

 Average case − An average number of steps taken on any instance of size a.

 Amortized − A sequence of operations applied to the input of size a averaged over


time.

 To solve a problem, we need to consider time as well as space complexity as the


program may run on a system where memory is limited but adequate space is
available or may be vice-versa. In this context, if we compare bubble sort and merge
sort.
 Bubble sort does not require additional memory, but merge sort requires additional
space. Though time complexity of bubble sort is higher compared to merge sort, we
may need to apply bubble sort if the program needs to run in an environment, where
memory is very limited.

 To solve a problem, we need to consider time as well as space complexity as the


program may run on a system where memory is limited but adequate space is
available or may be vice-versa


Asymptotic Analysis
Asymptotic analysis is an analysis of algorithms that focuses on

 Analyzing problems of large input size

 Consider only the leading term of the formula

 Ignore the coefficient of the leading term

 The asymptotic behavior of a function f(n) refers to the growth of f(n) as n gets large.

 We typically ignore small values of n, since we are usually interested in estimating


how slow the program will be on large inputs.

 Lower order terms contribute lesser to the overall cost as the input grows larger

e.g f(n) = 2n2+ 100n

f(1000)= 2(1000)2+ 100(1000) = 2,000,000+ 100,000

f(100000)= 2(100000)2+ 100(100000) = 20,000,000,000 + 10,000,000

 Hence, lower order terms can be ignored

 Such a term is called a growth term(rate of growth, order of growth, order of


magnitude) nThe most common growth terms can be ordered as follows (note that
many others are not shown)

O(1) < O(log n) < O(n) < O(nlog n) < O(n2) < O(n3) < O(2n) < …

“fastest” “slowest”

Leading Terms
a ( n) = ½ n + 4

Leading term: ½ n

b ( n) = 240 n + 0.001 n2

Leading term: 0.001 n2

c ( n) = n lg( n) + lg( n) + n lg( lg( n) )

Leading term: n lg( n)

Note that lg( n) = log2 ( n )

Sequential search analysis

 Suppose we have an array of n elements [1: 𝑛], and a key element, KEY.

 The following program is a simple loop which goes through the array sequentially
until it

 either finds the key, or determines that it is not found. (dtype is the type declaration
for the array.)

int SequentialSearch (dtype 𝐴[ ], int 𝑛, dtype 𝐾𝐸𝑌) {

for 𝑖 = 1 𝑡𝑜 𝑛 {

𝑖𝑓 (𝐾𝐸𝑌 == 𝐴[𝑖])

return (𝑖);

};

return (−1); //The for-loop ended and the key was not found.

 Let us analyze the number of key-comparisons (highlighted) in this algorithm. By


counting this dominant operation, basically we are counting the number of times the
loop is executed. There are two common ways of doing the analysis:

 Worst-case analysis: This determines the maximum amount of time the algorithm
would ever take. This analysis is usually easier than the average-case analysis. At the
same time, it is hoped that it is a good reflection of overall performance.
 Average-case analysis: This method determines the overall average performance. It
considers all possible cases, assigns a probability to each case, and computes the
weighted average (called expected value) for the random variable (in this case, the
number of key-comparisons).

Worst-Case Analysis of Sequential Search

 The worst-case number of key-comparison in this algorithm is obviously 𝑛. This


happens if the key is found in the last position of the array, or if it is not found
anywhere.

 Since each iteration of the for-loop takes at most some constant amount of time, C,
then the total worst-case time of the algorithm is (𝑛) ≤ 𝐶𝑛 + 𝐷.

 (The constant 𝐷 represents the maximum amount of time for all statements that are
executed only once, independent of the variable 𝑛. ) This total time is characterized as
“order of” 𝑛, denoted as O(𝑛).

Binary search

 Problem

 Find x in a sorted array T[1…n], if x is in T, output x in the subscript j of T; if x is not


in T, output j=0.

Analysis

 Compare the key recorded in the middle position of the table with the search key.

 If the two are equal, the search is successful; otherwise, use the middle position record
to divide the table into two sub-tables. If the key recorded in the middle position is
greater than the search key, Then further search the previous sub-table, otherwise
further search the next sub-table. Repeat the above process until a record that meets
the conditions is found, and the search is successful, or until the sub-table does not
exist, the search is unsuccessful at this time.

l=1,r=n;//l, r is the array boundary

while(l<r){

int mid=(l+r)/2;
if(T[mid]<x){

l=mid+1;

else{

r=mid;

Analysis

 Time complexity: O (logn)

Problem

 Write two retrieval algorithms:


Find x in a sorted array T[1…n], if x is in T, output x in the subscript j of T; if x is not
in T, output j =0.

Analysis

 One, order search


Sequential search is also called linear search. It belongs to an unordered search
algorithm and is suitable for linear tables whose storage structure is sequential
structure or chain storage.
Start from one end of the linear table of data structure, scan sequentially, and compare
the scanned node keys with the given search x. If they are equal, the search is
successful. If no value equal to x is found, the search fails.

Two, binary search


 Binary search, also known as binary search, is an ordered search algorithm and is
suitable for ordered lists.

 Select the middle node of the sequence table, compare the given x value with the key
of the middle node of the sequence, if they are equal, the search is successful; if not,
judge the x value and the middle node For the size of the point, select the correct
segment and compare the intermediate values until the intermediate node that is equal
to the value of x is found or there is no intermediate node in the table.

//Sequential search:

for (i = 0; i < n; ++i) {

if (t[i] == key) {

cout << "The search is successful! The subscript is:" << i+1 << endl;

break;

//Binary search:

left = 0; right = n - 1;

while ( left <= right) {

middle = (left+right) / 2;

if (key == t[middle]) {

cout << "The search is successful! The subscript is:" << middle + 1 << endl;

break;
}

else if (key < t[middle])

right = middle - 1;

else

left = middle + 1;

Analysis

 Sequence search time complexity: O(n)

 Binary search time complexity: O(log n)

You might also like