Algorithm

An algorithm is a finite sequence of well-defined, unambiguous steps used to solve a

problem or perform a computation. It takes input, processes it through logical steps, and
produces the desired output.

“An algorithm is a step-by-step procedure for solving a problem in a

finite amount of time.”
Characteristics of an Algorithm
1. Input – Accepts zero or more inputs.
2. Output – Produces at least one output.
3. Definiteness – Each step is clear and unambiguous.
4. Finiteness – Terminates after a finite number of steps.
5. Effectiveness – Each step is basic and executable.
6. Generality – Applicable to a class of problems.
Advantages of Algorithms
 Easy to understand and implement
 Language independent
 Helps in error detection and debugging
 Improves program efficiency
Disadvantages of Algorithms
 Time-consuming for complex problems
 Difficult to represent large logic clearly
 Not suitable for visual representation (flowcharts preferred)
Example (Simple Algorithm: Add Two Numbers)
1. Start
2. Read two numbers A and B
3. Compute C = A + B
4. Display C
5. Stop
Importance of Algorithms
 Foundation of computer programming
 Essential for problem-solving
 Improves performance and optimization
  Core to data structures, AI, and system design
Algorithms in Computing
Algorithms play a fundamental role in computing as they provide a systematic and
logical way to solve problems using computers. An algorithm is a finite set of well-
defined steps that transforms input into the desired output.
Key Roles of Algorithms in Computing
1. Problem Solving
o Algorithms define clear procedures to solve computational problems.
o They help break complex problems into smaller, manageable steps.
2. Efficiency and Performance
o Well-designed algorithms reduce time and memory usage.
o Algorithm efficiency directly affects system speed and scalability.
3. Foundation of Software Development
o All computer programs are built upon algorithms.
o Programming languages implement algorithms to perform tasks.
4. Data Processing and Analysis
o Algorithms enable sorting, searching, filtering, and analyzing large
datasets.
o Essential in databases, data mining, and big data applications.
5. Automation
o Algorithms automate repetitive and complex tasks without human
intervention.
o Used in robotics, process control, and workflow systems.
6. Decision Making
o Algorithms support logical and intelligent decision-making.
o Used in artificial intelligence, machine learning, and expert systems.
7. Security and Cryptography
o Algorithms ensure secure data transmission and storage.
o Used in encryption, authentication, and digital signatures.
8. Optimization
o Algorithms help find optimal solutions under constraints.
o Applied in scheduling, routing, and resource management.
 9. Real-Time Computing
o Algorithms enable fast responses in real-time systems.
o Used in embedded systems, IoT, and control systems.
10. Innovation and Research
o Algorithms drive advancements in emerging technologies.
o Core to AI, cloud computing, blockchain, and quantum computing.
Analyzing Algorithms
Analyzing algorithms is the process of evaluating an algorithm’s efficiency and
performance in terms of time and space requirements, independent of hardware and
programming language.
Purpose of Algorithm Analysis
 To predict performance before implementation
 To compare multiple algorithms for the same problem
 To select the most efficient algorithm
 To optimize resource usage
Types of Algorithm Analysis
1. Time Complexity
Measures the amount of time an algorithm takes to run as a function of input size n.
 Best Case – Minimum time required
 Average Case – Expected time for random inputs
 Worst Case – Maximum time required (most important)
Common Time Complexities:
 O(1) – Constant time
 O(log n) – Logarithmic time
 O(n) – Linear time
 O(n log n) – Linearithmic time
 O(n²), O(n³) – Polynomial time
 O(2ⁿ), O(n!) – Exponential time
2. Space Complexity
Measures the memory required by an algorithm, including:
 Input space
  Auxiliary (temporary) space
Asymptotic Notations
Used to describe algorithm growth rate for large input sizes.
1. Big-O (O) – Upper bound (worst case)
2. Big-Ω (Omega) – Lower bound (best case)
3. Big-Θ (Theta) – Tight bound (exact growth)
Factors Affecting Algorithm Performance
 Input size
 Input type (sorted, random, reverse)
 Algorithm design technique
 Data structures used
Example
Linear Search
 Best Case: O(1)
 Worst Case: O(n)
 Average Case: O(n)
Importance of Algorithm Analysis
 Ensures scalability
 Improves system performance
 Saves time and memory
 Essential for competitive programming and system design
Designing Algorithms
Designing algorithms is the process of developing a step-by-step logical procedure
to solve a given problem efficiently and correctly before writing the actual program.
Steps in Designing an Algorithm
1. Problem Definition
o Clearly understand the problem.
o Identify inputs, outputs, and constraints.
2. Problem Analysis
o Break the problem into smaller sub-problems.
o Study data size and complexity requirements.
 3. Algorithm Design
o Choose a suitable design strategy.
o Define clear steps using pseudocode or flowcharts.
4. Correctness Verification
o Ensure the algorithm produces correct output for all valid inputs.
o Check boundary and special cases.
5. Efficiency Analysis
o Analyze time and space complexity.
o Optimize if needed.
6. Implementation
o Convert the algorithm into a program using a programming language.
7. Testing and Refinement
o Test with sample and real-world inputs.
o Modify to improve performance and readability.
Common Algorithm Design Techniques
1. Brute Force
o Tries all possible solutions.
o Simple but inefficient.
2. Divide and Conquer
o Divides problem into sub-problems and combines solutions.
o Example: Merge Sort, Quick Sort.
3. Greedy Method
o Makes locally optimal choices.
o Example: Prim’s, Kruskal’s algorithms.
4. Dynamic Programming
o Solves overlapping sub-problems and stores results.
o Example: Fibonacci, Knapsack problem.
5. Backtracking
o Builds solution step by step and backtracks if needed.
o Example: N-Queens, Sudoku.
 6. Branch and Bound
o Prunes search space using bounds.
o Used in optimization problems.
Growth of Functions (Analysis of Algorithms)
Growth of functions describes how the running time or space requirement of an
algorithm increases as the input size (n) increases. It helps us compare algorithms
independent of hardware, language, or implementation details.
Why Growth of Functions is Important
 Predicts scalability of algorithms
 Compares efficiency for large inputs
 Ignores constants and lower-order terms
 Focuses on asymptotic behavior
Common Growth Rates (from best to worst)
Function Name Example

1 Constant Accessing an array element

log n Logarithmic Binary search

n Linear Linear search

n log n Linearithmic Merge sort, Quick sort (avg)

n² Quadratic Bubble sort

n³ Cubic Matrix multiplication

2ⁿ Exponential Recursive Fibonacci

n! Factorial Traveling Salesman (brute force)

Asymptotic Notations (used to express growth)
1. Big-O Notation O(f(n))
 Represents upper bound
 Worst-case performance
Example:
If T(n)= 3n² + 5n + 10 == O(n²)
2. Omega Notation Ω(f(n))
 Represents lower bound
 Best-case performance
Example:
Linear search best case → Ω(1)
3. Theta Notation Θ(f(n))
 Represents tight bound
 Exact growth rate
Example:
Merge sort → Θ(n log n)
Rules for Growth of Functions
 Ignore constants
→ O(2n) = O(n)
 Ignore lower-order terms
→ O(n² + n) = O(n²)
 Dominant term decides the growth
The major categories of algorithms are given below:
 Sort: Algorithm developed for sorting the items in a certain order.
 Search: Algorithm developed for searching the items inside a data structure.
 Delete: Algorithm developed for deleting the existing element from the data
structure.
 Insert: Algorithm developed for inserting an item inside a data structure.
 Update: Algorithm developed for updating the existing element inside a data
structure.

Algorithm Efficiency

Algorithm efficiency refers to how effectively an algorithm uses time and memory
resources as the input size increases. It is commonly measured using time complexity
and space complexity.

1. Best Case Complexity

 Definition: The minimum time (or steps) an algorithm takes for any input of size
n.
 It represents the most favourable input scenario.
 Denoted by Ω (Omega) notation.
 Useful to know the lower bound, but not very practical for real-world analysis.
Example:
 Linear Search
o If the element is found at the first position
 o Best case time complexity: Ω(1)
2. Worst Case Complexity
 Definition: The maximum time (or steps) an algorithm takes for any input of
size n.
 It represents the least favorable input scenario.
 Denoted by O (Big-O) notation.
 Most commonly used because it gives a guaranteed upper bound on
performance.
Example:
 Linear Search
o If the element is found at the last position or not found
o Worst case time complexity: O(n)
3. Average Case Complexity
 Definition: The expected time (or steps) taken by an algorithm over all possible
inputs of size n.
 Assumes all inputs are equally likely.
 Denoted by Θ (Theta) notation.
 More realistic than best case, but often difficult to compute.
Example:
 Linear Search
o On average, the element is found in the middle
o Average case time complexity: Θ(n)

Case Meaning Notation Practical Use

Best Case Minimum time Ω Low
Average Case Expected time Θ Moderate
Worst Case Maximum time O High

Divide and Conquer Approach

Idea
The array is divided into two halves:
1. Maximum subarray lies entirely in the left half
2. Maximum subarray lies entirely in the right half
 3. Maximum subarray crosses the midpoint
The maximum of these three cases is the answer.
Algorithm Steps
1. Divide the array into two halves at the midpoint.
2. Recursively find:
o Maximum subarray sum in the left half
o Maximum subarray sum in the right half
3. Find the maximum crossing subarray sum:
o Start from mid and extend leftwards (max left sum)
o Start from mid+1 and extend rightwards (max right sum)
4. Return the maximum of the three values.
Time Complexity Analysis
 Recurrence relation:
T(n) = 2T(n/2) + Θ(n)
 Using Master Theorem:
T(n) = Θ(n log n)
Space Complexity
 Due to recursion stack: O(log n)

Code:
def max(a, b, c=None):
if c is None:
return a if a > b else b
return max(max(a, b), c)
def maxCrossingSum(arr, l, m, h):
# Include elements on the left of mid
leftSum = float('-inf')
sum = 0
for i in range(m, l - 1, -1):
sum += arr[i]
leftSum = max(leftSum, sum)
 # Include elements on the right of mid
rightSum = float('-inf')
sum = 0
for i in range(m, h + 1):
sum += arr[i]
rightSum = max(rightSum, sum)
# Return the maximum of left sum, right sum, and their combination
return max(leftSum + rightSum - arr[m], leftSum, rightSum)
def MaxSum(arr, l, h):
if l > h:
return float('-inf')
if l == h:
# Base case: one element
return arr[l]
# Find the middle point
m = l + (h - l) // 2
# Return the maximum of three cases
return max (
MaxSum(arr, l, m),
MaxSum(arr, m + 1, h),
maxCrossingSum(arr, l, m, h),
)
def maxSubarraySum(arr):
return MaxSum(arr, 0, len(arr) - 1)
arr = [2, 3, -4, 5, 18]
print(maxSubarraySum(arr))
Strassens Matrix Multiplication
Strassen's Matrix Multiplication is the divide and conquer approach to solve the matrix
multiplication problems.
The usual matrix multiplication method multiplies each row with each column to
achieve the product matrix.
The time complexity taken by this approach is O(n3), since it takes two loops to
multiply. Strassens method was introduced to reduce the time complexity from O(n3) to
O(nlog 7).
Naive Method
First, we will discuss Naive method and its complexity.
Here, we are calculating Z=X Y.
Using Naive method, two matrices (X and Y) can be multiplied if the order of these
matrices are p q and q r and the resultant matrix will be of order p r.
The following pseudocode describes the Naive multiplication −
Algorithm: Matrix-Multiplication (X, Y, Z)
for i = 1 to p do
for j = 1 to r do
Z[i,j] := 0
for k = 1 to q do
Z[i,j] := Z[i,j] + X[i,k] × Y[k,j]
Complexity
Here, we assume that integer operations take O(1) time. There are three for loops in
this algorithm and one is nested in other. Hence, the algorithm takes O(n3) time to
execute.
Strassens Matrix Multiplication Algorithm
the time consumption can be improved a little bit.
Strassens Matrix multiplication can be performed only on square matrices where n is
a power of 2. Order of both of the matrices are n × n.
Divide X, Y and Z into four (n/2) × (n/2) matrices as represented below –

Z=
[ KI JL] , X=[ CA DB ] ,∧Y =[GE HF ]
Using Strassens Algorithm compute the following –
M1:=(A+C)×(E+F)
M2:=(B+D)×(G+H)
 M3:=(A−D)×(E+H)
M4:=A×(F−H)
M5:=(C+D)×(E)
M6:=(A+B)×(H)
M7:=D×(G−E)
Then,
I:=M2+M3−M6−M7
J:=M4+M6
K:=M5+M7
L:=M1−M3−M4−M5

Code:
import numpy as np
x = [Link]([[12, 34], [22, 10]])
y = [Link]([[3, 4], [2, 1]])
z = [Link]((2, 2))
m1, m2, m3, m4, m5, m6, m7 = 0, 0, 0, 0, 0, 0, 0
print("The first matrix is: ")
for i in range(2):
print()
for j in range(2):
print(x[i][j], end="\t")
print("\nThe second matrix is: ")
for i in range(2):
print()
for j in range(2):
print(y[i][j], end="\t")
m1 = (x[0][0] + x[1][1]) * (y[0][0] + y[1][1])
m2 = (x[1][0] + x[1][1]) * y[0][0]
m3 = x[0][0] * (y[0][1] - y[1][1])
m4 = x[1][1] * (y[1][0] - y[0][0])
m5 = (x[0][0] + x[0][1]) * y[1][1]
m6 = (x[1][0] - x[0][0]) * (y[0][0] + y[0][1])
m7 = (x[0][1] - x[1][1]) * (y[1][0] + y[1][1])

z[0][0] = m1 + m4 - m5 + m7
z[0][1] = m3 + m5
z[1][0] = m2 + m4
z[1][1] = m1 - m2 + m3 + m6
print("\nProduct achieved using Strassen's algorithm: ")
for i in range(2):
print()
for j in range(2):
print(z[i][j], end="\t")

Output
The first matrix is:
12 34
22 10

The second matrix is:

3 4
2 1

Product achieved using Strassen's algorithm:

104.0 82.0
86.0 98.0
RECURRENCES
Substitution Method for Recurrences:
The Substitution Method is a technique used to find the time complexity of recursive
algorithms by expanding the recurrence relation, identifying a pattern, and then proving
the result using mathematical induction.
  Understand how the recursion works.
 Write the recurrence relation.
 Guess the solution based on the recursion pattern.
 Verify the guessed solution using Mathematical induction.
Sample Code:
def fun(n):
if n <= 0:
return
print("GFG", end="")
fun(n // 2)
fun(n // 2)
Understanding the Recursion for This Code
 The function prints "GFG" once for each call.
 It makes two recursive calls, each with input size n/2.
 The recursion stops when n <= 0.