SEARCHING iii)Worst Case Time Complexity: O(n)

Searching is a technique to find the location of a given The element to be searched is either at last position or
element (search key) in an array or list. not present. The Worst case time complexity of the linear
search algorithm is O(n), where n is the number of elements
1) Linear Search / Sequential Search being searched.

Linear Search is a searching technique in which every element Best Case Average Case Worst Case
is compared with key element Linearly (Sequentially). Elements O(1) O(n) O(n)
can be in any order. It is also called sequential search. Linear
search performs equality comparisons. Input data need not to Space Complexity
be in sorted order. The space complexity of the Linear Search Algorithm is
O(1).

Time Complexity

i)Best Case Time Complexity: O(1)

The element to be searched is present at first position.
The best case time complexity of the linear search algorithm is
O(1) because only one comparison made.

ii)Average Case Time Complexity: O(n)

The average case time complexity of the linear search
algorithm is O(n), where n is the number of elements being
searched.

CS3401-ALGORITHMS (Sem-IV-R2021) - UNIT-I: 1

Example: Linear Search / Sequential Search 2) Binary Search
Binary Search is a searching algorithm for finding the position
of an element in a sorted array or list. It is also called half-
interval search. Binary search performs ordering comparisons.
Input data need to be in sorted order.

 The search key is compared with the middle element. If

match is found, then index of middle element is returned.
 If the middle element has a value greater than the key
value, then the left sub-array is searched. Otherwise, the
right sub-array is searched.
 This process is continued until the key is found or until the
size of a sub-array reduces to zero.

Time Complexity

i)Best Case Time Complexity: O(1)

The element to be searched is found in the first
comparison (element present exactly at the middle). The best
case time complexity of the binary search algorithm is O(1)
because only one comparison made.

CS3401-ALGORITHMS (Sem-IV-R2021) - UNIT-I: 2

ii)Average Case Time Complexity: O(log n) 3) Interpolation Search
The average case time complexity of the binary search
algorithm is O(log n). Interpolation Search is a searching algorithm that uses an
interpolation formula to estimate the position of an element in
iii)Worst Case Time Complexity: O(log n) a sorted array or list.
Worst case of the binary search occurs until the size of a
sub-array reduces to zero. The Worst case time complexity of The elements should be in a sorted order and uniformly
the binary search algorithm is O(log n). distributed.

Best Case Average Case Worst Case

O(1) O(log n) O(log n)
log(n) cuts input size by some constant factor  In a loop, calculate the value of “mid” using the probe
position formula.
Space Complexity  If it is a match, return the index of the mid.
The space complexity of the Binary Search Algorithm is  If the element is less than arr[mid], calculate the probe
O(1). position of the left sub-array. Otherwise, calculate the
same in the right sub-array.
Example: Binary Search  Repeat until a match is found or the sub-array reduces to
zero.

CS3401-ALGORITHMS (Sem-IV-R2021) - UNIT-I: 3

 iii)Worst Case Time Complexity: O(n)
In worst case, elements are sorted but distributed
exponentially. The Worst case time complexity of the
interpolation search algorithm is O(n).

Best Case Average Case Worst Case

O(1) O(log (log n)) O(n)
log(n) cuts input size by some constant factor
log(log(n)) cuts the input by a square root at each step

Space Complexity
The space complexity of the interpolation Search
Algorithm is O(1).

Time Complexity

i)Best Case Time Complexity: O(1)

In best case, elements are sorted and uniformly
distributed. The element to be searched is found in the first
probe itself. The best case time complexity of the interpolation
search algorithm is O(1).

ii)Average Case Time Complexity: O(log (log n))

In average case, elements are sorted and uniformly
distributed. The average case time complexity of the
interpolation search algorithm is O(log (log n)), where n is total
number of elements in array or list.

CS3401-ALGORITHMS (Sem-IV-R2021) - UNIT-I: 4

Example: Interpolation Search PATTERN SEARCH / PATTERN MATCH / STRING MATCH
Given a string of n characters called the text and a string of m
characters called the pattern, search the occurrences of pattern in
text. This process is continued until the match is found or until the
entire text is searched.
1) The Naive String-Matching Algorithm
Element to search: 4  The Naive String-Matching Algorithm approach tests all the
possible occurrences of Pattern P [1.......m] relative to text T
[1......n].
mid= 0 + [ (4-1)(8-0) / (15-1) ]  Try shift s = 0, 1.......n-m
mid= (3) (8) / 14  For each shift s (n - m +1 possible value of s), Compare
mid = 24 / 14
mid=1.7 => 1
T [s+1.......s+m] to P [1......m].

a[mid]=2
since a[mid]<4
search the right half

mid= 2 + [ (4-4)(8-2) / (15-4) ]

mid= 2+ [ (0) (6) / 11 ]
mid= 2+ [ 0 / 11 ]
mid=2

Time Complexity
a[mid]=4 Best Case Average Case Worst Case
since a[mid]=4 O(n) O(n) O(n*m)
Element found. Return index 2.

Comparisons:
((n-m+1)*m)
CS3401-ALGORITHMS (Sem-IV-R2021) - UNIT-I: 5
Example: The Naive String-Matching Algorithm Search
Suppose T = 1011101110
P = 111
Find all the Valid Shift.

Valid Shifts: s=2 and s=6. Thus, pattern matching can be obtained.

CS3401-ALGORITHMS (Sem-IV-R2021) - UNIT-I: 6

Example: The Naive String-Matching Algorithm Search

Show the comparisons the naive string matcher makes for the pattern
P = 0001 in the text T = 000010001010001.

Valid Shifts: s=1, s=5 and s=11. Thus, pattern matching can be obtained.

CS3401-ALGORITHMS (Sem-IV-R2021) - UNIT-I: 7

 2) Rabin-Karp Algorithm Example 1: Working modulo q=11, how many spurious hits does the
 The Rabin-Karp string matching algorithm calculates a hash Rabin-Karp matcher encounter in the text T=31415926535 when
value (hashing technique) for the pattern (P) and for each looking for the pattern P=26?
subsequence of text (T) to be compared.
 If the hash values are unequal, the algorithm will determine T = 31415926535
P = 26
the hash value for next subsequence of text (T).
T.Length =11
 If the hash values are equal, the algorithm will analyze the
and P mod Q = 26 mod 11 = 4
pattern (Character Matching).
Now find the exact match of P mod Q
 Character Matching is only required when the hash values
match.

d=decimal value
q=prime number
m=window size
CS3401-ALGORITHMS (Sem-IV-R2021) - UNIT-I: 8
 Example 2:
Text: a b b c a a c a
Pattern: a c a

P = aca = 1*102 + 3*101 + 1*100 = 131

T1 = abb = 1*102 + 2*101 + 2*100 = 122

T2 = bbc = 2*102 + 2*101 + 3*100 = 223
T3 = bca = 2*102 + 3*101 + 1*100 = 231
T4 = caa = 3*102 + 1*101 + 1*100 = 311
T5 = aac = 1*102 + 1*101 + 3*100 = 113
T6 = aca = 1*102 + 3*101 + 1*100 = 131

h(p)=h(T6)
aca = aca

The pattern occurs with T6

There is no Spurious Hit.

Spurious Hit
 A spurious hit occurs when the hash value of the pattern
matches the hash value of the text, but the text differs from
the pattern.
 Spurious hit increases the time complexity of the algorithm.
In order to minimize spurious hit, use modulus.

Time Complexity
Best Case Average Case Worst Case
O(n + m) O(n + m) O(n*m)

Comparisons:
Spurious Hit occurs with shift 3 (15), shift 4 (59) and shift 5 (92) ((n-m+1)*m)
Spurious Hit: Totally 3 shifts

CS3401-ALGORITHMS (Sem-IV-R2021) - UNIT-I: 9

 3) Knuth-Morris-Pratt Algorithm
With Text 'T', Pattern 'P' and Prefix Function 'Π' as inputs, find
the occurrence of Pattern 'P' in Text 'T’.

KMP algorithm compares character by character from left to

right. But whenever a mismatch occurs, it uses "Prefix Table(Π)
or LPS Table" to avoid the repeated comparison of characters and
backtracking on the “Text” never occurs.

Prefix Table is also known as LPS Table. LPS stands for

"Longest proper Prefix which is also Suffix".

Time Complexity

Computing Prefix Function(Π) O(m)

Matching Pattern(P) in Text(T) O(n) Example: Compute Π for the pattern ‘p’ below:

Time Complexity O(m+n)

m ←length [P] ← 7
n is the text length and m is the pattern length.
Prefix Table(Π) or LPS Table

CS3401-ALGORITHMS (Sem-IV-R2021) - UNIT-I: 10

Example: Given a string ‘T’ and pattern ‘P’ as follows:

n ←length [T] ← 15
m ←length [P] ← 7

CS3401-ALGORITHMS (Sem-IV-R2021) - UNIT-I: 11

 Total number of shifts for the match to be found = i-m = 13 - 7 = 6 shifts.

Pattern Match found at starting position Text[7]

CS3401-ALGORITHMS (Sem-IV-R2021) - UNIT-I: 12

 SORTING Example: Insertion Sort
Sorting algorithm is used to arrange elements of an array
or list in a specific order.
 Ascending Order: Elements are arranged from Low Value to
High Value (Increasing Order)
 Descending Order: Elements are arranged from High Value to
Low Value (Decreasing Order)

1) Insertion Sort
Insertion sort is a sorting algorithm that insert an unsorted element
in the correct position in each iteration.

Insertion sort works similar to the sorting of playing cards in hands.

The array is split into a sorted and an unsorted part. Values from the
unsorted part are picked and placed in the correct position in the
sorted part.

CS3401-ALGORITHMS (Sem-IV-R2021) - UNIT-I: 13

 Time Complexity

i)Best Case Time Complexity: O(n)

It occurs when there is no sorting required (the array is
already sorted). When the array is already sorted, the outer loop
runs for 'n' number of times whereas the inner loop does not
run at all. The best-case time complexity of insertion sort is
O(n).

ii)Average Case Time Complexity: O(n2)

It occurs when the array elements are in random order
(neither ascending nor descending). The average case time
complexity of insertion sort is O(n2).

iii)Worst Case Time Complexity: O(n2)

It occurs when the array elements are required to be
sorted in reverse order. The worst-case time complexity of
insertion sort is O(n2).

Best Case Average Case Worst Case

O(n) O(n2) O(n2)

Space Complexity
The space complexity of insertion sort is O(1). In
Insertion sort, an extra variable is required for swapping.

CS3401-ALGORITHMS (Sem-IV-R2021) - UNIT-I: 14

 2) Heap Sort Example: Heap Sort

Heap Sort Algorithm First, we have to construct a heap from the given array and convert
a) Build a heap from the given input array. it into max heap.
b) Repeat the following steps until the heap contains only
one element:
 Swap the root element of the heap (which is the
largest element) with the last element of the heap.
 Remove the last element of the heap (which is now
in the correct position).
 Heapify the remaining elements of the heap.

After converting the given heap into max heap, the array elements
are:

In the next step, we have to delete the root element (89) from the max
heap. To delete this node, we have to swap it with the last node (11).

After swapping the array element 89 with 11 and converting the heap
into max-heap, the elements of array are:

CS3401-ALGORITHMS (Sem-IV-R2021) - UNIT-I: 15

In the next step, we have to delete the root element (81) from the max In the next step, again we have to delete the root element (54) from
heap. To delete this node, we have to swap it with the last node (54). the max heap. To delete this node, we have to swap it with the last
node (14).

After swapping the array element 81 with 54 and converting the heap
into max-heap, the elements of array are: After swapping the array element 54 with 14 and converting the heap
into max-heap, the elements of array are:

In the next step, we have to delete the root element (76) from the max
heap. To delete this node, we have to swap it with the last node (9). In the next step, again we have to delete the root element (22) from
the max heap. To delete this node, we have to swap it with the last
node (11).

After swapping the array element 76 with 9 and converting the heap
into max-heap, the elements of array are: After swapping the array element 22 with 11 and converting the heap
into max-heap, the elements of array are:

CS3401-ALGORITHMS (Sem-IV-R2021) - UNIT-I: 16

In the next step, again we have to delete the root element (14) from Time Complexity
the max heap. To delete this node, we have to swap it with the last The time complexity of heap sort is O(n logn) in all three cases
node (9). (best case, average case, and worst case). The height of a
complete binary tree having n elements is logn.

i)Best Case Time Complexity: O(n logn)

It occurs when there is no sorting required (the array is
already sorted). The best-case time complexity of heap sort is
After swapping the array element 14 with 9 and converting the heap O(n logn).
into max-heap, the elements of array are –
ii)Average Case Time Complexity: O(n logn)
It occurs when the array elements are in random order
(neither ascending nor descending). The average case time
In the next step, again we have to delete the root element (11) from
the max heap. To delete this node, we have to swap it with the last
complexity of heap sort is O(n log n).
node (9).
iii)Worst Case Time Complexity: O(n logn)
It occurs when the array elements are required to be
sorted in reverse order. The worst-case time complexity of heap
After swapping the array element 11 with 9, the elements of array sort is O(n log n).
are:
Best Case Average Case Worst Case
O(n logn) O(n logn) O(n logn)
Now, heap has only one element left. After deleting it, heap will be
empty. Space Complexity
The space complexity of Heap sort is O(1).

After completion of sorting, the array elements are -

Now, the array is completely sorted.

CS3401-ALGORITHMS (Sem-IV-R2021) - UNIT-I: 17

1) What do you mean by algorithm? 5) Write down the properties of Asymptotic notations.
An algorithm is a sequence of unambiguous (clear) instructions Reflexivity
for solving a problem in a finite amount of time. If f(n) is given, then f(n) = O(f(n))
o Input Symmetry
o Output f(n) = Θ(g(n)) if and only if g(n) = Θ(f(n))
Transitivity
o Definiteness
f(n) = O(g(n)) and g(n) = O(h(n)) ⇒ f(n) = O(h(n))
o Finiteness Transpose Symmetry
o Effectiveness f(n) = O(g(n)) if and only if g(n) = Ω(f(n))

2) Write about notion of algorithm 6) Define the asymptotic notation “Big oh” (O)
O(f(n)) represents an upper bound on the growth rate of a
function f(n). ( f(n) ≤ C * g(n) for all n, n≥K )
O notation represents the worst-case scenario for the running
time or space complexity of an algorithm.

7) Define the asymptotic notation “Omega” ( Ω)

Ω(f(n)) represents a lower bound on the growth rate of a
function f(n). ( f(n) ≥ C * g(n) for all n, n≥K )
Ω notation represents the best-case scenario for the running
3) What is Algorithm analysis? How do you measure the
time or space complexity of an algorithm.
performance and efficiency of an algorithm?
Analysis the complexity of an algorithm is known as Algorithm
8) Define the asymptotic notation “Theta” (θ)
analysis.
Θ(f(n)) represents an upper and lower bound on the growth rate
 Time Complexity (Time required): indicates how fast the
of a function f(n). (C1*g(n) ≤ f(n) ≤ C2 * g(n) for all n, n≥K )
algorithm runs.
Θ notation represents the average-case scenario for the
It is the amount of computer time required by an algorithm
running time or space complexity of an algorithm.
to run.
 Space Complexity (Space required): indicates how much
9) What is recurrence relation?
extra memory the algorithm needs.
 Recurrence Relation is an equation that defines a
It is the amount of computer memory required by an
sequence recursively.
algorithm to run.
T(n)=T(n-1)+n for n>0 (Recurrence Relation)
T(0)=0 (Initial Condition)
4) Define asymptotic notations.  To solve a Recurrence Relation means to obtain a
Asymptotic notations are mathematical tools to represent the function that satisfy the recurrence.
time complexity of algorithms for Asymptotic analysis.
 Significance of Recurrence Relations
 Big oh (O) - Worst-Case scenario o Algorithm Analysis
 Omega (Ω) - Best-Case scenario o Performance Comparison
 Theta (θ) - Average-Case scenario o Optimization
CS3401-ALGORITHMS (Sem-IV-R2021) - UNIT-I: 18
10) How do you measure time complexity of an algorithm? 13) Define Lower Bound Theory.
Worst Case Analysis (Mostly Used)  Lower Bound Theory Concept is based upon the
 O notation represents the worst-case scenario for the calculation of minimum time that is required to
running time or space complexity of an algorithm. execute an algorithm is known as a Lower Bound
 O(f(n)) represents an upper bound on the growth rate of a Theory or Base Bound Theory.
function f(n).
 The main aim is to calculate a minimum number of
Best Case Analysis (Very Rarely Used)
comparisons required to execute an algorithm.
 Ω notation represents the best-case scenario for the
running time or space complexity of an algorithm.  Techniques used by Lower Bound Theory are:
 Ω(f(n)) represents a lower bound on the growth rate of a  Comparisons Trees
function f(n).  Oracle and adversary argument
Average Case Analysis (Rarely Used)  State Space Method
 Θ notation represents the average-case scenario for the
running time or space complexity of an algorithm. 14) Prove that f(n) = O(g(n)) and g(n) = O(h(n)) ⇒ f(n) = O(h(n))
 Θ(f(n)) represents an upper and lower bound on the growth If f(n)=n, g(n)=n2 and h(n)=n3
rate of a function f(n). N is O(n2) and n2 is O(n3) then n is O(n3)
Similarly this properties satisfies both Θ and Ω notations.
11) Write down the methods to solve Recurrence Relations.
There are four methods for solving Recurrence Transitivity Property of Asymptotic Notation
 Substitution Method f(n) = O(g(n)) and g(n) = O(h(n)) ⇒ f(n) = O(h(n))
 Iteration Method
 Recursion Tree Method 15) What is searching?
 Master Method Searching is a technique to find the location of a given
element (search key) in an array or list.
12) What is Substitution Method?  Linear Search
The Substitution Method Consists of two main steps:  Binary Search
 Guess the Solution.  Interpolation Search
 Use the mathematical induction to find the boundary
condition and shows that the guess is correct. 16) Outline the linear search algorithm.
Types: Forward Substitution and Backward Substitution

Solve Recurrence Relations by Substitution Method.

We have to show that it is asymptotically bound by O (log n).

CS3401-ALGORITHMS (Sem-IV-R2021) - UNIT-I: 19

17) Outline the binary search algorithm. 20) Difference between binary and interpolation search.

Binary Search Interpolation Search

It is also called half-interval It is also called half-interval
search. search (Using Interpolation
Formula).
Input data need to be in Input data need to be in
sorted order but distribution sorted order and
of data need not to be distribution of data need to
uniform. be uniform.
18) Outline the interpolation search algorithm.

21) Discuss the time and space complexity of linear search,

binary search and interpolation search.

Linear Search
Time Complexity
Best Case Average Case Worst Case
O(1) O(n) O(n)
Space Complexity: O(1)
Binary Search
Time Complexity
19) Difference between linear and binary search. Best Case Average Case Worst Case
Linear Search Binary Search
O(1) O(log n) O(log n)
Linear search performs Binary search performs
equality comparisons ordering comparisons Space Complexity: O(1)
It is also called sequential It is also called half-interval Interpolation Search
search. search. Time Complexity
Input data need not to be in Input data need to be in Best Case Average Case Worst Case
sorted order. sorted order. O(1) O(log (log n)) O(n)
Space Complexity: O(1)

CS3401-ALGORITHMS (Sem-IV-R2021) - UNIT-I: 20

22) What is pattern matching? 25) Outline the Knuth-Morris-Pratt (KMP) Algorithm.
Pattern Search / Pattern Match / String Match
Given a string of n characters called the text and a string of
m characters called the pattern, search the occurrences of
pattern in text. This process is continued until the match is
found or until the entire text is searched.
 The Naive String-Matching Algorithm
 Rabin-Karp Algorithm
 Knuth-Morris-Pratt (KMP) Algorithm

23) Outline the Naive String-Matching Algorithm.

26) Discuss the time complexity of pattern matching

algorithm.
Naive String-Matching Algorithm
24) Outline the Rabin-Karp Algorithm.

Rabin-Karp Algorithm

Knuth-Morris-Pratt (KMP) Algorithm

CS3401-ALGORITHMS (Sem-IV-R2021) - UNIT-I: 21

27) What is Sorting? 30) Discuss the time and space complexity of Insertion Sort
Sorting algorithm is used to arrange elements of an array or and Heap Sort.
list in a specific order. Insertion Sort
 Insertion Sort Time Complexity
 Heap Sort Best Case Average Case Worst Case
O(n) O(n2) O(n2)
28) Outline the Insertion Sort Algorithm.
Space Complexity: O(1)
Insertion sort works similar to the sorting of playing cards in
Heap Sort
hands. The array is split into a sorted and an unsorted part. Time Complexity
Values from the unsorted part are picked and placed in the Best Case Average Case Worst Case
correct position in the sorted part. O(n logn) O(n logn) O(n logn)
Space Complexity: O(1)

29) Outline the Heap Sort Algorithm.

1) Build a heap from the given input array.
2) Repeat the following steps until the heap contains only
one element:
 Swap the root element of the heap (which is the
largest element) with the last element of the
heap.
 Remove the last element of the heap (which is
now in the correct position).
 Heapify the remaining elements of the heap.

CS3401-ALGORITHMS (Sem-IV-R2021) - UNIT-I: 22