COEP Technological University
Aparna Biswas
Teaching Scheme: Lectures: 3 hours/week Self-Study: 1 hour/week
Examination Scheme: Theory: MSE: 30 Marks, TA: 10 marks, ESE: 60 marks
Unit 1: Mathematical Foundation: Growth of functions – Asymptotic notation, Standard notation and
common functions, Summations, solving recurrences.
Unit 2: Analysis of Algorithms: Necessity of time and space requirement analysis of algorithms, Worst case
analysis of common algorithms and operations on elementary data structures (e.g. Heapsort), Average case
analysis of Quicksort, Amortized analysis.
Unit 3: Standard Design Techniques-I :Divide and Conquer, Greedy method.
Unit 4: Standard Design Techniques-II: Dynamic programming, Graphs and Traversals.
Unit 5: Standard Design Techniques-III : Backtracking, Branch-and-bound.
Unit 6: Complexity Theory :Lower-bound arguments, Introduction to NP-Completeness, Reducibility (SAT,
3VC, Independent Set, Subset Sum, Hamiltonian Circuit etc), Introduction to approximation algorithms.
Text Book: Thomas Cormen et al., “Introduction to Algorithms” , PHI
Reference Book: E. Horowitz and S. Sahni. “Fundamentals of Computer Algorithms” , Galgotia,
COEP Technological University
Aparna Biswas
Algorithms and its characteristics
Need for Algorithms
Steps required for Algorithms
Use of the algorithms
Analysis of algorithms and importance
Growth of Function-Asymptotic Notation
COEP Technological University
Aparna Biswas
An algorithm is a finite sequence of well-defined instructions that can be used to solve a
computational problem.
It provides a step-by-step procedure that convert an input into a desired output.
Algorithm logical structure:
o Input: The algorithm receives input data.
o Processing: The algorithm performs a series of operations on the input data.
o Output: The algorithm produces the desired output.
COEP Technological University
Aparna Biswas
COEP Technological University
Aparna Biswas
Algorithms are essential for solving complex computational problems efficiently and
effectively. It provide a systematic approach to:
◦ Solving problems: Algorithms break down problems into smaller, manageable steps.
◦ Optimizing solutions: Algorithms find the best or near-optimal solutions to
problems.
◦ Automating tasks: Algorithms can automate repetitive or complex tasks, saving time
and effort.
◦ Efficiency--Consistency--Scalability—Automation--Standardization
COEP Technological University
Aparna Biswas
Define the problem: Clearly state the problem to be solved.
Design the algorithm: Choose an appropriate algorithm design paradigm and develop a
step-by-step procedure.
Implement the algorithm: Translate the algorithm into a programming language.
Test and debug: Execute the algorithm with various inputs to ensure its correctness and
efficiency.
Analyze the algorithm: Determine its time and space complexity and compare it to
alternative algorithms.
COEP Technological University
Aparna Biswas
Computer Science: Algorithms form the basis of computer programming and are used
to solve problems ranging from simple sorting and searching to complex tasks such as
artificial intelligence and machine learning.
Mathematics: Algorithms are used to solve mathematical problems, such as finding the
optimal solution to a system of linear equations or finding the shortest path in a graph.
Operations Research: Algorithms are used to optimize and make decisions in fields
such as transportation, logistics, and resource allocation.
Artificial Intelligence: Algorithms are the foundation of artificial intelligence and
machine learning, and are used to develop intelligent systems that can perform tasks
such as image recognition, natural language processing, and decision-making.
Data Science: Algorithms are used to analyze, process, and extract insights from large
amounts of data in fields such as marketing, finance, and healthcare.
COEP Technological University
Aparna Biswas
Algorithm analysis 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. Focused on CPU (time) usage, Memory usage, Disk Usage, and
Network usage.
The most concern is about the CPU time.
◦ Performance: How much time/memory/disk/etc. is used when a program is run.
This depends on the machine, compiler, etc.
◦ Complexity: The resource requirements of a program or algorithm scale.
COEP Technological University
Aparna Biswas
To predict the behavior of an algorithm without implementing it on a specific computer.
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.
It is impossible to predict the exact behavior of an algorithm.
More importantly, by analyzing different algorithms, we can compare them to determine
the best one for our purpose.
COEP Technological University
Aparna Biswas
Best case: Define the input for which algorithm takes less time or minimum time.
Worst Case: Define the input for which algorithm takes a long time or maximum time.
Average case: In the average case take all random inputs and calculate the computation
time for all inputs divided by the total number of inputs.
COEP Technological University
Aparna Biswas
Mathematical tools used to analyze the performance of algorithms by understanding
how their efficiency changes as the input size grows.
Asymptotic analysis allows for the comparison of algorithms’ space and time
complexities by examining their performance characteristics as the input size varies.
These notations provide a concise way to express the behavior of an algorithm’s time or
space complexity as the input size approaches infinity.
Rather than comparing algorithms directly, asymptotic analysis focuses on
understanding the relative growth rates of algorithms’ complexities.
It enables comparisons of algorithms’ efficiency by abstracting away machine-specific
constants and implementation details, focusing instead on fundamental trends.
COEP Technological University
Aparna Biswas
Big-O Notation (O-notation)
It specifies the upper bound of a function.
The maximum time required by an algorithm or the worst-case time complexity.
It returns the highest possible output value(big-O) for a given input.
O(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ f(n) ≤ cg(n) for all
n ≥ n0 }
Examples
{100 , log (2000) , 10^4 } O(1)
{ (n/4) , (2n+3) , (n/100 + log(n)) } O(n)
{ (n^2+n) , (2n^2) , (n^2+log(n))} O( n^2)
COEP Technological University
Aparna Biswas
Omega Notation (Ω-Notation)
The execution time serves as a lower bound on the algorithm’s time complexity.
It is defined as the condition that allows an algorithm to complete statement execution in
the shortest amount of time.
Ω(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ cg(n) ≤ f(n) for all
n ≥ n0 }
Examples
{ (n^2+n) , (2n^2) , (n^2+log(n))} Ω( n^2)
{ (n/4) , (2n+3) , (n/100 + log(n)) } Ω(n)
{ 100 , log (2000) , 10^4 } Ω(1)
COEP Technological University
Aparna Biswas
Theta Notation (Θ-Notation)
Theta notation encloses the function from above and below.
It represents the upper and the lower bound of the running time of an algorithm
It is used for analyzing the average-case complexity of an algorithm.
Θ (g(n)) = {f(n): there exist positive constants c1, c2 and n0 such that 0 ≤ c1 * g(n) ≤ f(n) ≤
c2 * g(n) for all n ≥ n0}
Example:
3n3 + 6n2 + 6000 = Θ(n3)
COEP Technological University
Aparna Biswas
COEP Technological University
Aparna Biswas
General Properties
If f(n) is O(g(n)) then a*f(n) is also O(g(n)), where a is a constant.
Transitive Properties
If f(n) is O(g(n)) and g(n) is O(h(n)) then f(n) = O(h(n))
Reflexive Properties
If f(n) is given then f(n) is O(f(n)). Maximum value of f(n) will be f(n) itself.
Symmetric Properties
If f(n) is Θ(g(n)) then g(n) is Θ(f(n))
This property only satisfies for Θ notation.
Transpose Symmetric Properties
If f(n) is O(g(n)) then g(n) is Ω (f(n))
This property only satisfies O and Ω notations.
COEP Technological University
Aparna Biswas
If f(n) = O(g(n)) and f(n) = Ω(g(n)) then f(n) = Θ(g(n))
If f(n) = O(g(n)) and d(n)=O(e(n)) then f(n) + d(n) = O( max( g(n), e(n) ))
If f(n)=O(g(n)) and d(n)=O(e(n)) then f(n) * d(n) = O( g(n) * e(n))
COEP Technological University
Aparna Biswas
The space complexity of an algorithm is the total space taken by the algorithm with
respect to the input size. Space complexity includes both Auxiliary space and space used
by input.
Space complexity is a parallel concept to time complexity.
Space Complexity= Auxiliary space+ input variables space
COEP Technological University
Aparna Biswas
It provides a high-level understanding of how an algorithm performs with respect to
input size.
It is a useful tool for comparing the efficiency of different algorithms and selecting the
best one for a specific problem.
It helps in predicting how an algorithm will perform on larger input sizes, which is
essential for real-world applications.
Asymptotic analysis is relatively easy to perform and requires only basic mathematical
skills.
COEP Technological University
Aparna Biswas
Asymptotic analysis does not provide an accurate running time or space usage of an
algorithm.
It assumes that the input size is the only factor that affects an algorithm’s performance,
which is not always the case in practice.
Asymptotic analysis can sometimes be misleading, as two algorithms with the same
asymptotic complexity may have different actual running times or space usage.
It is not always straightforward to determine the best asymptotic complexity for an
algorithm, as there may be trade-offs between time and space complexity.
COEP Technological University
Aparna Biswas
Thank You…
COEP Technological University
Aparna Biswas
