What is algorithm?
An algorithm is a finite sequence of well-defined instructions to solve a problem or perform a
computation.
It can be understood as a recipe for a computer program, providing the specific steps to execute to
get the desired output.
NEED OF THE ALGORITHMS :
Algorithms are used to solve problems or automate tasks in a systematic and efficient manner. They
are a set of instructions or rules that guide the computer or software in performing a particular task
or solving a problem.
There are several reasons why we use algorithms:
Efficiency: Algorithms can perform tasks quickly and accurately, making them an essential
tool for tasks that require a lot of calculations or data processing.
Consistency: Algorithms are repeatable and produce consistent results every time they are
executed. This is important when dealing with large amounts of data or complex processes.
Scalability: Algorithms can be scaled up to handle large datasets or complex problems, which
makes them useful for applications that require processing large volumes of data.
Automation: Algorithms can automate repetitive tasks, reducing the need for human
intervention and freeing up time for other tasks.
Standardization: Algorithms can be standardized and shared among different teams or
organizations, making it easier for people to collaborate and share knowledge
Analysis of algorithm
Purpose: To evaluate and compare the efficiency of different algorithms for solving the same
problem.
Time Complexity: Measures the amount of time an algorithm takes to complete as a function of the
input size, often expressed using Big O notation.
Space Complexity: Measures the amount of memory or storage an algorithm uses as a function of
the input size.
Why Analysis of Algorithms is important?
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. Analysis of algorithms is the determination of the amount of time and space resources
required to execute it.
To predict the behaviour of an algorithm for large inputs (Scalable Software).
It is much more convenient to have simple measures for the efficiency of an algorithm than
to implement the algorithm and test the efficiency every time a certain parameter in the
underlying computer system changes.
More importantly, by analysing different algorithms, we can compare them to determine
the best one for our purpose.
Type of Complexity
Time Complexity: The time complexity of an algorithm quantifies the
amount of time taken by an algorithm to run as a function of the length
of the input. Note that the time to run is a function of the length of the
input and not the actual execution time of the machine on which the
algorithm is running on.
The valid algorithm takes a finite amount of time for execution. The time
required by the algorithm to solve given problem is called time
complexity of the algorithm. Time complexity is very useful measure in
algorithm analysis.
It is the time needed for the completion of an algorithm. To estimate
the time complexity, we need to consider the cost of each fundamental
instruction and the number of times the instruction is executed.
Space Complexity:
Definition -
Problem-solving using computer requires memory to hold temporary
data or final result while the program is in execution. The amount of
memory required by the algorithm to solve given problem is called space
complexity of the algorithm.
The space complexity of an algorithm quantifies the amount of space
taken by an algorithm to run as a function of the length of the input.
Consider an example: Suppose a problem to find the frequency of array
elements.
It is the amount of memory needed for the completion of an algorithm.
To estimate the memory requirement we need to focus on two parts:
(1) A fixed part: It is independent of the input size. It includes memory
for instructions (code), constants, variables, etc.
(2) A variable part: It is dependent on the input size. It includes memory
for recursion stack, referenced variables, etc.
Types of Analysis
Algorithms are typically analyzed under three cases:
a) Best Case
Minimum number of operations.
Example: Searching in a list — finding the item at the first position.
b) Worst Case
Maximum number of operations.
This is the most commonly used because it guarantees performance.
c) Average Case
Expected behavior over all possible inputs.
Often more realistic but harder to compute
a. Best Case Analysis
The best case represents the minimum number of operations an
algorithm [Link] happens when the input is arranged in the most
favorable way.
Purpose
• Shows the fastest possible performance.
• Not often used alone because it may be unrealistic.
Example: Linear Search
Finding an element in an array:
[10, 20, 30, 40, 50]
Suppose we search for 10 (first element).
• Only 1 comparison needed.
• Running time = O(1) (constant time)
This is the best case situation — the item is exactly where we want it.
b. Worst Case Analysis
The worst case represents the maximum number of operations an
algorithm may perform.
This occurs when the input is arranged in the least favorable way.
Purpose
Most commonly used.
Guarantees performance.
Ensures the algorithm will not perform worse than this bound.
Example: Linear Search
Searching for an element not present:
[10, 20, 30, 40, 50]
Search for 90 (not in the list).
Must check every element in the list.
Number of comparisons = n
Running time = O(n)
This is the worst case, because we examine the entire list.
c. Average Case Analysis
The average case measures the expected running time of an algorithm
over all possible
inputs of size n.
It calculates probability-weighted performance.
More realistic than best or worst case.
Shows how an algorithm performs typically.
Why is it harder to compute?
Because it requires:
Knowledge of input distribution (how likely each input is)
Mathematical probability calculation
What is Running Time Analysis ?
It is the process of determining how processing time of a problem
increases as the size of the problem (input size) increases. Input size is
the number of elements in the input, and depending on the problem
type, the input may be of different types.
Example:
• Size of an array
• Polynomial degree
• Number of elements in matrix
• Number of bits in the binary representation of the input
• Vertices and edges in the graph
Running time analysis of algorithms
Running time analysis, also known as time complexity analysis, is a way to
estimate the efficiency of an algorithm in terms of the time it takes to execute
as a function of the input size. The goal is to understand how the algorithm’s
performance scales with larger inputs
Asymptotic Notations For Running Time Analysis
• Big-O Notation:This notation gives the tight upper bound of the given
function. Generally, it is represented as f(n)=O(g(n)). That means at
larger values of N the upper bound of a f(n) is g(n).
• For example: if f(n) = n^4 + 2n^3 + 100n + 500 is the given algorithm
then n 4 is g(n).
• That means g(n) gives the maximum rate of growth for f(n) at larger
values of n.
• eg Linear search , worst case
F(n)<=c.g(n)
n>=n0
C>0, n0>=1
F(n)=O(g(n))
• Big-θ Notation: This notation decides whether the upper and the lower
bound of the given function(algorithm) are the same. The average
running time of an algorithm is always between the lower bound and the
upper bound. If the upper bound(O) and the lower bound(Ω) give the
same result, then the Θ notation will also have the same rate of growth.
As an example, let us assume that f(n) = 10n+ n is the expression. Then,
its tight upper bound g(n) is O(n). The rate of growth in the best case is
g(n) = O(n).
• Big-Ω Notation: Similar to the O discussion, this notation gives the
tighter lower bound of the given algorithm and we represent it as f(n) =
Ω(g(n)). That means, at larger values of n, the tighter lower bound of f(n)
is g(n).
• For example, if f(n) = 100n2+10n+50, g(n) is Ω(n2).
Estimating Running Time / Counting Number of Steps (On Paper)
This is an important skill used in algorithm analysis. The goal is to
compute how many times a basic operation executes.
Step 1: Identify the basic operation
The basic operation is the one that runs most frequently (e.g.,
comparison, assignment).
Step 2: See how many times loops run
• Simple loops → run n times
• Nested loops → multiply the number of iterations
• Logarithmic loops → divide n repeatedly → O(log n)
Step 3: Add operations
If there are multiple independent loops:
• Add their complexities
If there are nested loops:
• Multiply their complexities
Step 4: Apply asymptotic notation
Ignoring:
• constants
• lower-order terms
Time
Code Type Steps
Complexity
Single loop n O(n)
Nested loops (n × n) n² O(n²)
Nested triangular loop n(n+1)/2 O(n²)
Divide by 2 / binary log₂ n O(log n)
Constant statement 1 O(1)
Multiple independent loops n+n O(n)
Linear Loop
for (i = 1; i <= n; i++) {
x = x + 1;
}
• Loop runs n times
• Basic operation runs n times
• Running time = O(n)
Example 2: Nested Loop (Square Growth)
Code:
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
count++;
}
}
Step-by-step:
1. Basic operation: count++
2. Inner loop runs n times for each outer loop iteration.
3. Outer loop also runs n times.
4. Total operations = n × n = n²
5. Asymptotic time = O(n²)
Nested Loop With Different Ranges
Code:
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= i; j++) {
sum++;
}
}
Step-by-step:
Outer loop: i = 1 to n
Inner loop: j = 1 to i → number of operations varies
Total operations:
1+2+3+…+n=2/n(n+1)
Asymptotically:
𝑛(𝑛 + 1)
= 𝑂(𝑛2 )
2
Logarithmic Loop
Code:
while (n > 1) {
n = n / 2;
}
Step-by-step:
Each iteration makes n half:
n → n/2 → n/4 → n/8 → ... → 1
Number of times we can divide by 2 until reaching 1 = log₂(n)
So:
Steps = log₂ n
Running time = O(log n)
Explanation:
This is very efficient; growth is slow.
Bubble Sort:
1. Time complexity: O(n^2) in the worst and average cases, O(n) in the best
case (when the
input array is already sorted)
Space complexity: O(1)
1. Basic idea: Iterate through the array repeatedly, comparing adjacent pairs of
elements and
swapping them if they are in the wrong order. Repeat until the array is fully
sorted.
Bubble Sort:
Advantages:
Simple implementation, works well for small datasets, requires only constant
space, stable sorting algorithm
Disadvantages:
Inefficient for large datasets, worst-case time complexity of O(n^2), not
optimal for partially sorted datasets.
How bubble sort works
[Link] and swap: The algorithm goes through the list, comparing each pair
of adjacent elements.
[Link] if necessary: If the elements are in the wrong order (e.g., the first
element is greater than the second for ascending order), they are swapped.
3. Repeat passes: This process is repeated for all adjacent pairs in the list.
After the first pass, the largest element will be in its correct final position at the
end of the list.
4. Continue until sorted: Subsequent passes continue, but each pass can skip
the already sorted elements at the end. The algorithm finishes when a full pass
is completed without any swaps, which indicates the list is sorted.
BubbleSort(A, n):
for i = 0 to n-1:
for j = 0 to n-i-2:
if A[j] > A[j+1]:
swap A[j] and A[j+1]
Manual Run Through
Before we implement the Bubble Sort algorithm in a programming language,
let’s manually run
through a short array only one time, just to get the idea.
Step 1: We start with an unsorted array.
[7, 12, 9, 11, 3]
Step 2: We look at the two first values. Does the lowest value come first? Yes,
so we don’t need to
swap them.
[7, 12, 9, 11, 3]
Step 3: Take one step forward and look at values 12 and 9. Does the lowest
value come first? No.
[7, 12, 9, 11, 3]
Step 4: So we need to swap them so that 9 comes first.
[7, 9, 12, 11, 3]
Step 5: Taking one step forward, looking at 12 and 11.
[7, 9, 12, 11, 3]
Step 6: We must swap so that 11 comes before 12.
[7, 9, 11, 12, 3]
Step 7: Looking at 12 and 3, do we need to swap them? Yes.
[7, 9, 11, 12, 3]
Step 8: Swapping 12 and 3 so that 3 comes first.
[7, 9, 11, 3, 12]
Example for self-study:
1. 4,5,8,7,12,15
2. 6,35,36,75,41
Selection Sort:
1. Time complexity: O(n^2) in all cases (worst, average, and best)
Space complexity: O(1)
2. Basic idea: Find the minimum element in the unsorted portion of the array and swap it with
the first unsorted element. Repeat until the array is fully sorted.
Advantages:
Simple implementation, works well for small datasets, requires only constant space, in-place sorting
algorithm
Disadvantages:
Inefficient for large datasets, worst-case time complexity of O(n^2), not optimal for partially sorted
datasets, not a stable sorting algorithm
Algorithm Steps
1. Find the minimum in unsorted portion.
2. Swap it with the first element of unsorted part.
3. Move boundary of sorted part forward.
4. Repeat.
SelectionSort(A, n):
for i = 0 to n-1:
minIndex = i
for j = i+1 to n-1:
if A[j] < A[minIndex]:
minIndex = j
swap A[i] and A[minIndex]
Manual Run Through
Before we implement the Selection Sort algorithm in a programming language, let's manually run
through a short array only one time, just to get the idea.
Step 1: We start with an unsorted array.
[ 7, 12, 9, 11, 3]
Step 2: Go through the array, one value at a time. Which value is the lowest? 3, right?
[ 7, 12, 9, 11, 3]
Step 3: Move the lowest value 3 to the front of the array.
[ 3, 7, 12, 9, 11]
Step 4: Look through the rest of the values, starting with 7. 7 is the lowest value, and already at the
front of the array, so we don't need to move it.
[ 3, 7, 12, 9, 11]
Step 5: Look through the rest of the array: 12, 9 and 11. 9 is the lowest value.
[ 3, 7, 12, 9, 11]
Step 6: Move 9 to the front.
[ 3, 7, 9, 12, 11]
Step 7: Looking at 12 and 11, 11 is the lowest.
[ 3, 7, 9, 12, 11]
Step 8: Move it to the front.
[ 3, 7, 9, 11, 12]
Finally, the array is sorted.
Example for self-study:
1. 4,5,23.76,7,12,15
2. 6,5,35,54,75,41
Insertion Sort
The Insertion Sort algorithm uses one part of the array to hold the sorted values, and the other part
of the array to hold values that are not sorted yet.
Time complexity: O(n^2) in the worst and average cases, O(n) in the best case (when the input array
is already sorted) Space complexity: O(1)
Basic idea: Build up a sorted subarray from left to right by inserting each new element into its
correct position in the subarray. Repeat until the array is fully sorted.
Advantages: Simple implementation, works well for small datasets, requires only constant space,
efficient for partially sorted datasets, stable sorting algorithm
Disadvantages: Inefficient for large datasets, worst-case time complexity of O(n^2)
How it works:
1. Take the first value from the unsorted part of the array.
2. Move the value into the correct place in the sorted part of the array.
3. Go through the unsorted part of the array again as many times as there are values.
for i in range(1,n):
insert_index = i
current_value = my_array.pop(i)
for j in range(i-1, -1, -1):
if my_array[j] > current_value:
insert_index = j
my_array.insert(insert_index, current_value)
Manual Run Through
Before we implement the Insertion Sort algorithm in a programming language, let's manually run
through a short array, just to get the idea.
Step 1: We start with an unsorted array.
[ 7, 12, 9, 11, 3]
Step 2: We can consider the first value as the initial sorted part of the array. If it is just one value,
it must be sorted, right?
[ 7, 12, 9, 11, 3]
Step 3: The next value 12 should now be moved into the correct position in the sorted part of
the array. But 12 is higher than 7, so it is already in the correct position.
[ 7, 12, 9, 11, 3]
Step 4: Consider the next value 9.
[ 7, 12, 9, 11, 3]
Step 5: The value 9 must now be moved into the correct position inside the sorted part of the
array, so we move 9 in between 7 and 12.
[ 7, 9, 12, 11, 3]
Step 6: The next value is 11.
[ 7, 9, 12, > 11, 3]
Step 7: We move it in between 9 and 12 in the sorted part of the array.
[ 7, 9, 11, 12, 3]
Step 8: The last value to insert into the correct position is 3.
[ 7, 9, 11, 12, 3]
Step 9: We insert 3 in front of all other values because it is the lowest value.
[ 3,7, 9, 11, 12]
Finally, the array is sorted.
Example for self-study:
1. 4,5,23.76,7,12,15
2. 6,5,35,54,75,41
Comparison:
1. Bubble Sort, Selection Sort, and Insertion Sort all have the same worst-case and average-
case time complexity of O(n²). However, Insertion Sort generally performs better in practice,
especially on nearly sorted data, due to fewer swaps and comparisons, making it more
efficient in average scenarios compared to Bubble Sort and Selection Sort.
2. Insertion Sort has the best-case time complexity of O(n) when the input array is already
sorted, which is not possible for Bubble Sort and Selection Sort.
3. Selection Sort and Insertion Sort both have the same space complexity of O(1), while Bubble
Sort also has a space complexity of O(1).
4. Bubble Sort and Insertion Sort are stable sorting algorithms, meaning that they preserve the
relative order of equal elements in the sorted array, while Selection Sort is not stable.
In terms of performance, Insertion Sort tends to perform better than Bubble Sort and Selection Sort
for small datasets, while Bubble Sort and Selection Sort may perform better than Insertion Sort for
larger datasets or datasets that are partially sorted.
Overall, each algorithm has its own advantages and disadvantages, and the choice of which
algorithm to use depends on the specific requirements of the problem at hand.
Searching algorithms
Searching algorithms are essential tools in computer science used to locate
specific items within a collection of data. In this tutorial, we are mainly going
to focus upon searching in an array. When we search an item in an array,
there are two most common algorithms used based on the type of input
array.
Linear Search : It is used for an unsorted array. It mainly does one by one
comparison of the item to be search with array elements. It takes linear or O(n)
Time.
Binary Search : It is used for a sorted array. It mainly compares the array's
middle element first and if the middle element is same as input, then it
returns. Otherwise it searches in either left half or right half based on
comparison result (Whether the mid element is smaller or greater). This
algorithm is faster than linear search and takes O(Log n) time.
Linear Search:
How it works:
1. Go through the array value by value from the start.
2. Compare each value to check if it is equal to the value we are looking for.
3. If the value is found, return the index of that value.
4. If the end of the array is reached and the value is not found, return -1 to
indicate that the value was not found.
To implement the Linear Search algorithm we need:
1. An array with values to search through.
2. A target value to search for.
3. A loop that goes through the array from start to end.
4. An if-statement that compares the current value with the target value, and
returns the current index if the target value is found.
5. After the loop, return -1, because at this point we know the target value has
not been found.
def linearSearch(arr, targetVal):
for i in range(len(arr)):
if arr[i] == targetVal:
return i
return -1
Manual Run Through
Let's try to do the searching manually, just to get an even better understanding
of how Linear Search works before actually implementing it in a programming
language. We will search for value 11.
Step 1: We start with an array of random values.
[ 12, 8, 9, 11, 5, 11]
Step 2: We look at the first value in the array, is it equal to 11?
[ 12, 8, 9, 11, 5, 11]
Step 3: We move on to the next value at index 1, and compare it to 11 to see if
it is equal.
[ 12, 8, 9, 11, 5, 11]
Step 4: We check the next value at index 2.
[ 12, 8, 9, 11, 5, 11]
Step 5: We move on to the next value at index 3. Is it equal to 11?
[ 12, 8, 9, 11, 5, 11]
We have found it!
Value 11 is found at index 3.
Returning index position 3.
Linear Search is finished.
Binary Search
The Binary Search algorithm searches through an array and returns the index of the
value it searches for.
How it works:
1. Check the value in the center of the array.
2. If the target value is lower, search the left half of the array. If the target value
is higher, search the right half.
3. Continue step 1 and 2 for the new reduced part of the array until the target
value is found or until the search area is empty.
4. If the value is found, return the target value index. If the target value is not
found, return -1.
5. Manual Run Through
Let's try to do the searching manually, just to get an even better understanding of
how Binary Search works before actually implementing it in a programming
language. We will search for value 11.
Step 1: We start with an array.
[ 2, 3, 7, 7, 11, 15, 25]
Step 2: The value in the middle of the array at index 3, is it equal to 11?
[ 2, 3, 7, 7, 11, 15, 25]
Step 3: 7 is less than 11, so we must search for 11 to the right of index 3. The
values to the right of index 3 are [ 11, 15, 25]. The next value to check is the
middle value 15, at index 5.
[ 2, 3, 7, 7, 11, 15, 25]
Step 4: 15 is higher than 11, so we must search to the left of index 5. We have
already checked index 0-3, so index 4 is only value left to check.
[ 2, 3, 7, 7, 11, 15, 25]
We have found it!
Value 11 is found at index 4.
Returning index position 4.
Binary Search is finished.
To implement the Binary Search algorithm we need:
1. An array with values to search through.
2. A target value to search for.
3. A loop that runs as long as left index is less than, or equal to, the right index.
4. An if-statement that compares the middle value with the target value, and
returns the index if the target value is found.
5. An if-statement that checks if the target value is less than, or larger than, the
middle value, and updates the "left" or "right" variables to narrow down the
search area.
6. After the loop, return -1, because at this point we know the target value has
not been found.
def binarySearch(arr, targetVal):
left = 0
right = len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == targetVal:
return mid
if arr[mid] < targetVal:
left = mid + 1
else:
right = mid - 1
return -1
Time complexity for Binary Search is
O(log2n)
Partition-based Selection Algorithm
Partition algorithms are key techniques in computer science, widely used in
sorting (like QuickSort) and selection problems. By dividing an array around a
pivot, they allow data to be organized into segments for faster sorting and
searching.
This tutorial covers popular partitioning methods, including Hoare’s and
Lomuto’s, each with unique strategies for arranging elements around a pivot.
Idea
1. Choose a pivot.
2. Partition the array into:
o Left: elements < pivot
o Pivot position
o Right: elements > pivot
3. Compare pivot index with k:
o If pivot index == k → pivot is the kth smallest
o If k < pivot index → recurse on left
o Else → recurse on right with updated k
Time Complexity
Average: O(n)
Worst case: O(n²) (when pivot is repeatedly smallest/largest)
Advantages
Very fast in practice.
Uses constant extra space.
Does not require the whole array to be sorted.
Disadvantages
Worst-case performance can degrade.
Depends on pivot choice.