UNIT 1
Unit – 1 Introduction: What is an Algorithm? Fundamentals of Algorithmic problem
solving, Fundamentals of the Analysis of Algorithm Efficiency, Analysis Framework,
Measuring the input size, Units for measuring Running time, Orders of Growth, Worst-
case, Best-case, Average case and Worst case efficiencies.
_________________________________________________________________________________
What is an algorithm?
Definition: An algorithm is defined as finite sequence of unambiguous instructions
followed to accomplish a given task. It is also defined as unambiguous, step by step
procedure (instructions) to solve a given problem in finite number of steps by
accepting a set of inputs and producing the desired output. After producing the result,
the algorithm should terminate. The notion of an algorithm is pictorially represented
as shown below:
Input
Problem ->Algorithm ->Program->Computer->Output
Observe the following activities to see how an algorithm is used to produce the
desired result:
• The solution to a given problem is expressed in the form of an algorithm.
• The algorithm is converted into a program.
• The program when it is executed, accept the input and produces the desired
output.
Properties of an algorithm : An algorithm must satisfy the following conditions.
• Input: Each algorithm should have zero or more inputs. The range of inputs
for which algorithm works should be satisfied
• Output: The algorithm should produce correct results. At least one output
has to be produced.
• Definiteness: Each instruction should be clear and unambiguous.
• Effectiveness: The instructions should be simple and should transform the
given input to the desired output.
• Finiteness: The algorithm must terminate after a finite sequence of
instructions.
TYPES OF ALGORITHMS
1. Brute Force Algorithm: A straightforward approach that exhaustively tries all possible
solutions, suitable for small problem instances but may become impractical for larger ones
due to its high time complexity.
2. Recursive Algorithm: A method that breaks a problem into smaller, similar
subproblems and repeatedly applies itself to solve them until reaching a base case,
making it effective for tasks with recursive structures.
3. Encryption Algorithm: Utilized to transform data into a secure, unreadable form using
cryptographic techniques, ensuring confidentiality and privacy in digital communications
and transactions.
4. Backtracking Algorithm: A trial-and-error technique used to explore potential solutions
by undoing choices when they lead to an incorrect outcome, commonly employed in
puzzles and optimization problems.
5. Searching Algorithm: Designed to find a specific target within a dataset, enabling
efficient retrieval of information from sorted or unsorted collections.
6. Sorting Algorithm: Aimed at arranging elements in a specific order, like numerical or
alphabetical, to enhance data organization and retrieval.
7. Divide and Conquer Algorithm: Breaks a complex problem into smaller
subproblems,solves them independently, and then combines their solutions to address
the original problem effectively.
Algorithm design and analysis process
A sequence of steps involved in designing and analyzing an algorithm is shown in the
figure below.:
• Understand the problem
• Decide on Computational Device Exact Vs Approximate Algorithms
• Algorithm Design Techniques
• Design an algorithms
• Prove Correctness
• Analyze the Algorithm
• Code the Algorithm
Understanding the Problem:
Begin by clearly understanding the problem you are trying to solve. Identify the input,
output, and constraints. This step is crucial for defining the scope of the algorithm.
Deciding on Computational Device:
Once you completely understand a problem, you need to ascertain the capabilities of
the computational device the algorithm is intended for. The vast majority of
algorithms in use today are still destined to be programmed for a computer.
The essence of this architecture is captured by the so-called random-access machine
(RAM). Its central assumption is that instructions are executed one after another, one
operation at a time. Accordingly, algorithms designed to be executed on such machines
are called sequential algorithms.
The central assumption of the RAM model does not hold for some newer computers
that can execute operations concurrently, i.e., in parallel. Algorithms that take
advantage of this capability are called parallel algorithms
Exact Vs. Approximate Algorithms:
Decide whether an exact solution is necessary or if an approximate solution
would suffice. Exact algorithms guarantee optimal solutions, while approximate
algorithms provide solutions that are close to optimal but might be obtained
faster.
Algorithm Design Techniques:
Choose appropriate algorithm design techniques based on the problem at hand.
Common techniques include:
• Divide and Conquer: Break the problem into smaller subproblems and solve
them independently.
• Dynamic Programming: Solve subproblems and store their solutions to avoid
redundant computations.
• Greedy Algorithms: Make locally optimal choices at each step with the hope of
finding a global optimum.
Design an Algorithm:
Develop the step-by-step procedure to solve the problem based on the chosen design
technique. Clearly define the algorithm's input, output, and the sequence of operations
to achieve the desired result.
Prove Correctness:
Provide a mathematical or logical proof that the algorithm produces the correct output
for any valid input. This step ensures the algorithm reliably solves the problem it was
designed for.
Analyze the Algorithm:
Assess the algorithm's efficiency, primarily in terms of time and space complexity.
Perform a worst-case, best-case, and average-case analysis to understand how the
algorithm performs under different scenarios.
Code the Algorithm:
Implement the algorithm in a programming language of choice. Pay attention to details,
and ensure that the code accurately reflects the designed algorithm. Test the algorithm
with various inputs to validate its correctness and efficiency.
FUNDAMENTALS OF ANALYSIS OF ALGORITHM EFFICIENCY
Fundamentals of Analysis of Algorithm involves the following factors :
1 Analysis of Framework
2 Measuring an input size
3 Units for measuring runtime
4 Worst case, Best case and Average case
5 Asymptotic Notations
1. ANALYSIS FRAME WORK
The main purpose of algorithm analysis is to design most efficient algorithms. Time and
space complexity depends on lots of things like hardware, operating system,
processors, etc. However, since space and other resources are cheaply available now,
we don't consider any of these factors while analyzing the algorithm. We will only
consider the execution time of an algorithm. The efficiency of an algorithm depends on
two factors:
1. Space efficiency
2. Time efficiency
Space efficiency: The space efficiency of an algorithm is the amount of memory
required to run the program completely and efficiently. If the efficiency is measured
with respect to the space (memory required), the word space complexity is often used.
The space requirement has fixed/static/compile time and a variable/dynamic/runtime
components. Fixed components are the machine language instructions and static
variables. Variable components are the runtime stack usage and dynamically allocated
memory usage.
Time efficiency : The time efficiency of an algorithm is measured purely on how fast a
given algorithm is executed. Since the efficiency of an algorithm is measured using
time, the word time complexity is often associated with an algorithm.
The time efficiency of the algorithm depends on various factors that are shown below:
Components that affect time efficiency
• Speed of the computer
• Choice of the programming language
• Compiler used
• Choice of the algorithm
• Number (Size) of inputs/Outputs
Since we do not have any control over speed of the computer, programming language
and compiler, let us concentrate only on next two factors such as: Choice of an
algorithm and Number (size) of inputs .
2. Measuring of Input size : An algorithm's efficiency as a function of some parameter
n indicating the algorithm's input size. In most cases, selecting such a parameter is
quite straightforward.
For example, it will be the size of the list for problems of sorting, searching, finding the
list's smallest element, and most other problems dealing with lists.
3. Units for measuring Running time
The running time of algorithms is often measured using different units depending on
the context and the granularity of analysis. Here are common units for measuring
running time:
• Seconds (s): The most straightforward unit, representing the actual time in seconds
that an algorithm takes to run on a specific machine. Suitable for measuring real-
world performance but can be influenced by external factors like the machine's
load. Milliseconds is a smaller unit than seconds, measuring time in thousandths of
a second. Useful for more precise measurement when algorithms have relatively
fast execution times.
• Instruction Count: The number of machine instructions executed by an algorithm.
Useful for low-level analysis and optimization, considering the specific machine
architecture.
• Basic Operation : The operation that contributes most towards the running time of
the algorithm is called basic operation. The number of times basic operation is
executed generally depends on size of the input. The basic operation is the most
time consuming operation in the algorithm. It is the statements present in the
innermost loop in the algorithm for example : addition operation while adding two
matrices, since it is present in innermost loop.
• Comparisons or Swaps:
For sorting algorithms, measuring the number of element comparisons or swaps
provides insight into their efficiency.
Relevant for algorithms where the primary operations involve comparisons or data
rearrangement.
Now, let us see ,how to compute the running time of an algorithm using basic operation
or How time efficiency is analyzed?. The time efficiency is analyzed by determining the
number of times the basic operation is executed.
The running time T(n) is given by:
T(n) ~ b*C(n)
• T is the running time of the algorithm
• n is the size of the input
• b execution time for basic operation.
• C represent number of times the basic operation is executed
Computing GCD
The notion of an algorithm can be explained by computing the GCD of two numbers.
Now, let us see “What is GCD of two numbers?”
Definition: The GCD (short form for Greatest Common Divisor) of two numbers m and n
denoted by GCD(m, n) is defined as the largest integer that divides both m and n such
that the remainder is zero. GCD of two numbers is defined only for positive integers but,
not defined for negative integers and floating point numbers. For example, GCD(10, 30)
can be obtained as shown below:
Step 1: The numbers 1, 2, 5, 10 divide 10
Step 2: The numbers 1, 2, 5, 6, 10 and 30 divide 30
Step 3: Observe from step I and step 2 that the numbers 1, 2, 5 and 10 are common
divisors of both 10 and 30 and 10 is the greatest number which is common and hence it
is called Greatest Common Divisor
So, GCD(10,30) = 10.
The GCD of two numbers can be computed using various methods as shown below:
• Euclid’s algorithm (Using modulus)
• Repetitive subtraction (Euclid’s algorithm)
• Consecutive inter checking algorithm
• Middle school procedure using prime factors.
Steps to Find GCD Using Euclidean Algorithm
Let a and b be two numbers such that a > b.
Divide the larger number a by, the smaller number b
Replace ‘a’ with ‘b’ and ‘b’ with the remainder from step-1
Repeat step-1 and step-2 until the remainder is zero.
Algorithm gcd(a, b):
Input : two positive integers a & b
Output : gcd of 2 numbers
Purpose/ description: this algorithm finds GCD of 2 numbers, a and b.
// If the second number is 0, the first number is the GCD
if b == 0:
return a
else
# Recursively call the function with 'b' and the remainder of 'a' divided by 'b'
return gcd(b, a % b).
Once you get the remainder 0, the divisor will be the GCD of a and b at this stage.
4. Orders of growth
Definition: Some algorithms execute faster for smaller values of n. But, as the value of
n increases, they tend to be very slow. So, the behaviour of some algorithm changes
with increase in value of n. This change in behaviour of the algorithm and algorithm's
efficiency can be analyzed by considering the highest order of n. The order of growth is
normally determined for larger values of n as the behaviour of algorithm changes as the
value of n increases .In real time applications we normally encounter large values of n
The order of growth of an algorithm is an approximation of the time required to run a
computer program as the input size increases. The order of growth ignores the constant
factor needed for
fixed operations and focuses instead on the operations that increase proportional to input
size. For example, a program with a linear order of growth generally requires double the
time if the input doubles.
The order of growth is often described using Big-O notation.
This table summarizes the most common orders of growth:
By comparing N (which is linear) and 2"(which is exponential) it is observed from the
above table that exponential function grows very fast even for small variation of N. So,
an algorithm with linear running time is preferred over an algorithm with exponential
running time. The basic efficiency of asymptotic classes are shown below:
1 or any constant: Indicates that running time of a program is constant.
log N: Indicates that running time of a program is logarithmic. This running time occurs
in programs that solve larger problems by reducing the problem size by a constant
factor at each iteration of the loop (For example, binary search).
N: Indicates that running time of a program is linear. So, when N is 1000, the running
time is 1000 units. When N is doubled, so does the running time. (For example linear
search)
N log N: Indicates that running time of a program is N log N (For lack adjective, it is used
as it is instead of linear, quadratic etc). The algorithm elements in ascending order such
as quick sort, merge sort and heap sort wave this running time. (These sorting
techniques are discussed in later chapters)
N2 : Indicates that running time of a program is quadratic. The algorithms normally will
have two loops. For example, sorting algorithms such as bubble sort, selection sort,
addition and subtraction of two matrices have this running time.
N3 : Indicates that running time of a program is cubic. The algorithms with running time
will have three loops. For example, matrix multiplication, algorithm to solve
simultaneous equations using gauss-elimination method will have this running time.
2N: Indicates that running time of an algorithm is exponential. The tower of Hanoi
problem and algorithms that generate subsets of a given set will have this running time
N! : Indicates that running time of an algorithm is factorial. All permutations of set will
have this running time.
Note: All the above functions can be ordered according to their order of growth (from
lowest to highest) as shown below:
1 < log(n) < n < n * log(n) < n2 < n3< 2n < n!
Note: Even though running times of 2N and N! are different, normally both classes are
considered as exponential.
Worst-case, Best-case and average case efficiencies
Does the algorithm efficiency depends on the size of algorithm's input alone? For some
of the problems, the time complexity will not depend on the number of inputs alone. For
example, while searching for a specific item in an array of n elements using linear
search, we have following three situations:
Worst case efficiency : The efficiency of an algorithm for the input of size n for which
the algorithm takes longest time to execute among all possible inputs is called worst
case efficiency For example, if we use linear search and the item to be searched is no
present in the array, then it is an example of worst case efficiency.
In the worst case, the algorithm runs for the longest duration among all possible inputs
for a given size. Here, maximum number of steps are executed for that input. It is
denoted using symbol Big(O)
Best case efficiency: The efficiency of an algorithm for the input of size n for which the
algorithm takes least time during execution among all possible inputs of that size is
called best case efficiency.
In the best case, the algorithm runs fastest for the input specified. For example, in
linear search, if the item to be searched is present in the beginning, then it is an
example of the best case efficiency.
Average case efficiency, in this the average number of basic operations executed will
be considered. This is required only for the randomized input.
So, knowing n alone itself is not enough to estimate the run time of an algorithm or a
function. In such cases, we may have to find the worst-case efficiency, best case
efficiency and average case efficiency.
Example: Searching for an Element in an Array
Suppose you have an array of numbers, and you want to find a specific element in that
array.
def search_element(arr, target):
for num in arr:
if num == target:
return True
return False
Now, let's analyze the efficiency of this algorithm in terms of worst-case, best-case,
and average-case scenarios.
Worst-case efficiency:
• This is the scenario where the algorithm takes the maximum amount of time to
complete. In our example, the worst-case scenario occurs when the target element is
at the end of the array or is not present in the array.
The worst-case time complexity is O(n), where n is the number of elements in the list.
Worst-case scenario
arr = [1, 2, 3, 4, 5]
target = 5
result = search_element(arr, target)
# In this case, the algorithm has to go through the entire array to find the target element.
Best-case efficiency:
•This is the scenario where the algorithm takes the minimum amount of time to
[Link] our example, the best-case scenario occurs when the target element is at
the beginning of the array.
•The best-case time complexity is O(1), as the algorithm may find the target element in
the first iteration.
# Best-case scenario
arr = [1, 2, 3, 4, 5]
target = 1
result = search_element(arr, target)
# In this case, the algorithm finds the target element in the first iteration.
Average-case efficiency: This is the scenario where the algorithm takes an average
amount of time to complete, considering all possible inputs.
The average-case time complexity is often more challenging to analyze and may involve
statistical analysis.
In our example, if the target element is equally likely to be anywhere in the array, the
average-case time complexity is O(n/2), which simplifies to O(n).
# Average-case
scenarioarr = [1, 2, 3, 4, 5]
target = 3
result = search_element(arr, target)
# On average, the algorithm might need to check half of the array element therefore
efiiciency will be 0( n/2).
UNIT 2
Asymptotic Notations and Basic Efficiency classes, Informal Introduction, O-
notation, Ω-notation, θ-notation, mathematical analysis of non-recursive
algorithms, mathematical analysis of recursive algorithms.
Asymptotic Notations: Asymptotic Notations are used to describe the running time of
an algorithm with respect to input size. It analyses an algorithm’s running time by
identifying its behaviour as its input size grows. These notations are helpful to compare
two algorithms based on changes in their performance as the input size is increased or
decreased.
The different types of asymptotic notations are :
• O(Big Oh)
• Ω(Big Omega)
• ΘbigTheta
Basic Efficiency classes ( Same as Orders of Growth)
The time efficiencies of a large number of algorithms fall into only a few classes. These
classes are listed in Table below in increasing order of their orders of growth, along with
their names and a few comments.
An algorithm from a better asymptotic efficiency class will outperform an algorithm
from a worse class even for moderately sized inputs.
Definitions of Asymptotic notations
Big-Oh(O) notation is used to define the upper bound of an algorithm in terms of Time
Complexity. That means Big - Oh notation always indicates the maximum time required
by an algorithm for all input values. It describes the worst case of an algorithm time
complexity.
Formally, Big - Oh Notation can be defined as follows:-
Assuming n indicates the size of input and g(n) is a growth function, then O(g(n)) is
defined as set of all functions with a small or same order of growth as g(n)) as n goes to
infinity.
Let f(n) be the time efficiency of an algorithm. The function f(n) is said to be O(g(n))
[read as big-oh of g(n)), denoted by f(n) = O(g(n))
If and only if there exists a positive constant c and positive integer n0 satisfying the
constraint
F(n) <=c*g(n) for all n≥ n0
Here, c .g(n) is the upper bound. The upper bound on f(n) indicates that function f(n) will
not consume more than the specified time c* g(n) i.e., running time of function f(n)
maybe equal to c .g(n), but it will never be worse than the upper bound. So, we can say
that f(n) is generally faster than g(n)
So, if we draw the graph f(n) and c*g(n) verses n, the graph of the function f(n) lies
Below the graph of c g(n) for sufficiently large value of n as shown below:
Big-O is the formal method of expressing the upper bound of an algorithm’s running
time. It is a measure of the longest amount of time it could possibly take for the
Algorithm to complete.
The function g(n) is normally expressed using higher order terms of f(n) This is achieved
using the following steps:
• Take the lower order term of f(n) replace the constant with next higher order variable.
Repeat this step, till we get the higher order term and call it as c .g(n)
• Once the constraint “ f(n) <= c.g(n) “ for n >= n0is obtained we say f(n) ∈ O(g(n))
To give a few examples, the following assertions are all true:
Indeed, the first two functions are linear and hence have a lower order of growth than
g(n) = n2, while the last one is quadratic and hence has the same order of growth as n2
Example: Let f(n) = 100n + 5 Express f(n) using big-oh
Solution: It is given that f(n) = 100n + 5 Replacing 5 with n (so that next higher order term
is obtained), we get 100n + n and call it c.g(n)
i.e..c.g(n) = 100n + n for n = 5
= 101n for n =5;
Now, the following constrain is satisfied:
f(n) <=c * g(n) for n ≥ n0
I .e.,100n+5<=101n for n >= 5
It is clear from the above relations that c = 101 g(n) = n and n0=5. So , by definition
f(n) ∈ O(g(n)) * I .e.., f(n) ∈ O(n)
Ω(Big-Omega)
Definition: Let f(n) be the time complexity of an algorithm. The function f(n) is said to be
Ω(g(n)) [read as big-omega of g(n)] which is denoted by f(n) = Ωg((n))
If and only if there exists a positive constant c and non-negative integer no satisfying the
constrain:
f(n)>=c*g(n) for all n≥ n0.
This notation gives the lower bound on a function f(n) within a constant factor. The
lower bound on f(n) indicates that function f(n) will consume at least the specified time
c*g(n)i.e., the algorithm has a running time that is always greater than c*g(n). In general,
the lower bound implies that below this time the algorithm cannot perform better.
So, if we draw the graph f(n) and c*g(n) verses n, the graph of f(n) lies above the graph of
g(n) for sufficiently large value of n as shown:
Example: Let f(n) = 100n+ 5. Express f(n) using big-omega
Solution: The constrain to be satisfied is
f(n) >=c* g(n) for n >= n0
i.e., 100n+5 ≥ 100 n for n>=0
It is clear from the above relations that c = 100. g(n) = n and n0 = 0. So, by definition
f(n) = Ω(g(n))i.e.,f(n) ∈ Ω(n)
Big-Theta
Definition: Let f(n) be the time complexity of an algorithm. The function f(n) is said to be
big-theta of g(n), denoted
f(n) = Θ(g(n))
if and only if there exists some positive constants c1, c2 and non-negative integer no
satisfying the constraint
c1*g(n)<=f(n)<=c2* g(n) for all n≥ n0.
So, if we draw the graph f(n), c1,*g(n) and c₂ g*(n) verses n, the graph of function f(n) lies
above the graph of c1*g(n) and lies below the graph of c2* g(n) for sufficiently large
value of n as shown below,
This notation is used to denote both lower bound and upper bound on a function f(n)
within a constant factor. The upper bound on f(n) indicates that function f(n) will not
consume more than the specified time cog(n).The lower bound on f(n) indicates that
function f(n) in the best case will consume at least the specified time c₁*g(n).
Useful Property Involving the Asymptotic Notations
If t1(n) ∈ O(g1(n)) and t2(n) ∈ O(g2(n)),
then t1(n) + t2(n) ∈ O(max{g1(n), g2(n)}) (also true for other two notations).
Proof :
Since t1(n) ∈ O(g1(n)), there exist some positive constant c1 and some non-negative
integer n1 such that
t1(n) ≤ c1g1(n) for all n ≥ n1.
Similarly, since t2(n) ∈ O(g2(n)),
t2(n) ≤ c2g2(n) for all n ≥ n2.
Let us denote c3 = max{c1, c2} and consider n ≥ max{n1, n2} so that we can use both
inequalities. Adding them yields the following:
t1(n) + t2(n) ≤ c1g1(n) + c2g2(n)
c3g1(n) + c3g2(n) = c3[g1(n) + g2(n)]
c3*2max{g1(n), g2(n)}.
Hence, t1(n) + t2(n) ∈ O(max{g1(n), g2(n)}), with the constants c and n0 required by the
O definition being 2*c3 = 2 max{c1, c2} and max{n1, n2}, respectively.
Mathematical analysis of non - recursive algorithms :
Non Recursive Function are procedures or subroutines implemented in a programming
language, whose implementation does not references itself.
Let us systematically apply the general framework to analyze the time efficiency of non-
recursive algorithms.
General Plan for Analyzing the Time Efficiency of Non recursive Algorithms:
1. Decide on a parameter (or parameters) indicating an input’s size.
2. Identify the algorithm’s basic operation (in the inner most oop).
3. Check whether the number of times the basic operation is executed
depends only on the size of an input. If it also depends on some additional
property, the worst-case, average-case, and, if necessary, best-case
efficiencies have to be investigated separately.
4. Set up a sum expressing the number of times the algorithm’s basic operation
is executed.
5. Using standard formulas and rules of sum manipulation either find a closed
form formula for the count or at the least, establish its order of growth.
EXAMPLE 1: Consider the problem of finding the value of the largest element
in a list of n numbers.
Mathematical analysis of non - recursive algorithms :
Recursion is the action of a function calling itself either directly or indirectly, and the
associated function is known as a recursive function. A recursive method can be used
to tackle some issues with relative ease. Factorial, Fibonacci, Towers of Hanoi (TOH), in
order/preorder/post order tree traversals, DFS of Graph, etc., are a few examples of
these issues. By calling a duplicate of itself and resolving the original problem's smaller
subproblems, a recursive function solves a specific problem.
The various types of recursion are shown below:
[Link] recursion
[Link] recursion
Direct recursion: A recursive function that invokes itself is said to have direct recursion.
For example, the factorial function calls itself (detailed explanation is given later) and
hence the function is said to have direct recursion.
Indirect recursion: A function which contains a call to another function which in turn
calls another function which in turn calls another function and so on and eventually
calls the first function is called indirect recursion.
The provided problem statement is split into two pieces to construct a recursive
algorithm.
Base Case: This is the simplest possible solution to the issue, consisting only of a
condition that ends the recursive function. When a specific condition is satisfied, the
result is evaluated in this base case.
Recursive Step: It calculates the outcome by making repeated calls to the same
function but with more minor or straightforward inputs.
General Plan for Analyzing the Time Efficiency of Recursive Algorithms
1. Decide on a parameter (or parameters) indicating an input’s size.
2. Identify the algorithm’s basic operation.
3. Check whether the number of times the basic operation is executed can vary
on different inputs of the same size; if it can, the worst-case, average-case,
and best-case efficiencies must be investigated separately.
4. Set up a recurrence relation, with an appropriate initial condition, for the
number of times the basic operation is executed.
5. Solve the recurrence or, at least, ascertain the order of growth of its solution.
EXAMPLE 1: Compute the factorial function F(n) = n! for an arbitrary non
negative integer n. Since n!= 1•. . . . • (n − 1) • n = (n − 1)! • n, for n ≥ 1 and
0!= 1 by definition, we can compute F(n) = F(n − 1) • n with the following
recursive algorithm.
ALGORITHM FACT(n)
//Purpose : Computes n! recursively
//Input: A nonnegative integer n
//Output: The value of n!
if n = 0 return 1
else return F(n − 1) * n
Tracing ( Factorial)
Example 2 :