Design and Analysis

of Algorithms
Arshi Parvaiz
Algorithms
● Finite set of steps to solve a problem is called algorithm.
● It takes a set of input(s) and produces the desired output. For example,
● An algorithm to add two numbers:
○ Take two number inputs
○ Add numbers using the + operator
○ Display the result
Analysis on nature of input size
● An algorithm may not have the same performance for different types of
inputs. With the increase in the input size, the performance will change.

● The study of change in performance of the algorithm with the change in

the order of the input size is defined as asymptotic analysis.

● Analyzing algorithms involve thinking about how their resource

requirements will scale with increasing input size.
➔ Space and time
● It is a a process of comparing two algorithms.
● Analysis is independent of machine.
Role of algorithms in Computing
Data processing:
● Algorithms are crucial for data management and analysis tasks.
● Algorithms play a key role in unlocking insights from big data sets.
● Sorting algorithms arrange data in specific orders, like alphabetical or
numerical.
● Searching algorithms help locate specific data within a dataset.
● They contribute to faster data processing and decision-making.
● Various algorithms are used based on the nature and size of the data.
● Continuous advancements in algorithms lead to improved data handling
capabilities.
● Efficient algorithms save time and resources in data processing workflows.
Role of algorithms in Computing
Problem solving:
● Algorithms are utilized for solving computational problems effectively.
● They address a range of problem types, including mathematical, optimization, and
decision-making problems.
● Mathematical algorithms tackle complex mathematical computations and equations.
● Optimization algorithms help find the best solution among a set of possible options.
● Decision-making algorithms assist in making informed choices based on available data.
● These algorithms are crucial for problem-solving in various domains.
● Continuous innovation in algorithms leads to improved problem-solving capabilities.
● Efficient algorithms contribute to more accurate and efficient problem-solving processes.
Role of algorithms in Computing
Computer graphics:
● Algorithms play a vital role in creating and processing images and graphics.
● Image compression algorithms reduce the size of image files without significant loss of
quality.
● Computer-generated graphics algorithms generate realistic and detailed graphics in
digital environments.
● These algorithms are essential for various applications, including video games,
animation, and graphic design.
● They enable efficient storage and transmission of visual data.
● Graphics processing algorithms enhance images by adjusting colors, sharpness, and
other visual aspects.
● Real-time rendering algorithms enable interactive and dynamic graphics display.
● Continuous advancements in graphics algorithms lead to more realistic and immersive
visual experiences.
Role of Algorithms in Computing
Artificial Intelligence
● Algorithms are foundational in the development of Artificial Intelligence (AI).
● AI encompasses various intelligent systems, including machine learning algorithms,
natural language processing (NLP) algorithms, and computer vision algorithms.
● Machine learning algorithms enable machines to learn from data without explicit
programming, covering tasks like classification, regression, clustering, and reinforcement
learning.
● NLP algorithms empower computers to understand, interpret, and generate human
language, aiding tasks such as sentiment analysis, language translation, speech
recognition, and text generation. One prime example is chatGPT.
● Computer vision algorithms allow machines to interpret and analyze visual data like
images and videos, supporting tasks such as object detection, image classification, image
segmentation, and facial recognition.
Role of Algorithms in Computing
Database management:
● Algorithms play a crucial role in database management, aiding in the
organization and handling of vast amounts of data.
● Indexing algorithms are utilized to efficiently retrieve and store data in
databases, improving search and retrieval times.
● Query optimization algorithms optimize database queries for faster
execution and resource utilization, enhancing overall database
performance.
● These algorithms are integral to ensuring data integrity, accessibility, and
efficiency within databases across various industries and applications.
Role of Algorithms in Computing
Network communication:
● Algorithms are essential for facilitating efficient communication and data
transfer within networks.
● Routing algorithms determine the optimal paths for data packets to travel
through a network, ensuring timely and reliable delivery.
● Error correction algorithms detect and correct errors that may occur
during data transmission, maintaining data integrity and reducing
retransmission rates.
● These algorithms are fundamental in enabling smooth and reliable
network operations, supporting various communication protocols and
network infrastructures.
Role of Algorithms in Computing
Operating systems:
● Algorithms are fundamental components of operating systems, serving various critical tasks.
● Process scheduling algorithms determine the order and priority of tasks (processes) to be
executed by the CPU, optimizing resource utilization and system responsiveness.
● Memory management algorithms handle the allocation and deallocation of memory resources
among processes, ensuring efficient use of available memory and preventing memory leaks.
● Disk management algorithms manage disk storage operations, including read/write operations,
file organization, and disk space allocation, to optimize disk performance and data retrieval.
● These algorithms are integral to the smooth and efficient operation of operating systems,
supporting multitasking, resource sharing, and overall system stability.
Time Complexity and Space Complexity
● In computer science algorithm complexity plays a crucial role in achieving
optimal performance.

● Developers need to consider both time efficiency and memory usage.

● It refers to the amount of data it needs to process in order to accomplish

its task effectively.
Asymptotic Notations
● Asymptotic notations is a mathematically way of representing time
complexity.

Big-O Notation
○ The Big-O notation describes the worst-case running time of a program.
○ Big-O of an algorithm by count how many iterations an algorithm will take in
the worst-case scenario with an input of N.
○ We typically consult the Big-O because we must always plan for the worst
case.
Big-O Notation (O-notation)
Big-O notation represents the upper

bound of the running time of an

algorithm. Thus, it gives the worst-case

complexity of an algorithm.
Omega Notation (Ω-notation)
Omega notation represents the lower

bound of the running time of an

algorithm. Thus, it provides the best

case complexity of an algorithm.

Theta Notation (Θ-notation)
Theta notation encloses the function from

above and below. Since 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.
Recursion and Recurrence Relations
 What is Recursion
The process in which a function calls itself directly or indirectly is called recursion
and the corresponding function is called a recursive function.
 Recurrence Relation
○ A recurrence relation is a mathematical expression that defines a sequence in
terms of its previous terms.
○ In the context of algorithmic analysis, it is often used to model the time
complexity of recursive algorithms.
Recursion and Recurrence Relations
 Fibonacci Series
 Factorial of a number
 Sum up all positive integers when input n is given
Fibonacci Sequence
● The Fibonacci Sequence:
○ 0, 1, 1, 2, 3, 5, 8, 13, 21
Time Complexity of Fibonacci
sequence using Recursion
● Best Case Complexity
● O(2n)
Time Complexity of Fibonacci
sequence using Recursion
● Worst Case Complexity
● Ω(2n/2)
Space Complexity
● Each state (except f(0) and f(1)) generates
two
● additional states
● Total number of states generated are 15.
● In general, total number of states are
approximately equal to 2^n for computing
n'th fibonacci number(f(n)).
● Each state denotes a function call to
'fibonacci()' which does nothing but to make
another recursive call.
Note that this does not always hold true and for
more accurate time complexity analysis. The
purpose of this explanation is to give you a
general idea about running time of recursive
algorithms.
Space Complexity
● Computing space complexity of recursive algorithm is little bit tricky.
● We need to understand how the stack frames are generated in memory
for recursive call sequence.
● Recursion relies on the stack to manage function calls and their contexts.
● Each function call adds a new stack frame, and each return removes the
topmost frame.
● The space complexity of the recursive Fibonacci algorithm is O(n) in
the worst case.
● This is because the number of stack frames maintained during the
recursion is proportional to the input size 'n', where 'n' represents the
index of the Fibonacci number to be computed.
Space Complexity
● For Example When computing Fibonacci(5), the recursive calls create stack
frames for Fibonacci(4), Fibonacci(3), Fibonacci(2), and Fibonacci(1).