Subject: ANALYSIS OF ALGORITHMS

Chipter#1: Introduction

Data Structure
Data: The collection of raw facts and figures.
A single item in data is called a data item.

Data Structure tells:

 How to store data

 How to access data
 How to manage data

Data Structure:
A branch of computer science that deals with organizing data in a way that allows efficient
storage, retrieval, and management.

Examples of Data Structures

Array, Linked List, Tree, Graph, Queue, Stack, etc.

Data Structure vs Algorithm

Data Structure:
A way of organizing and storing data in memory for efficient access and management.

Algorithm:
A step-by-step procedure or set of instructions used to process or work with data.

Why Learn Data Structures?

 Helps us become better programmers
 Enables writing efficient programs
 Improves problem-solving speed and effectiveness
 TYPES OF DATA STRUCTURE

CLASSIFICATION OF DATA STRUCTURES:

Primitive data structure: Primitive data types are basic built-in types that store a single value and are
directly supported by the programming language.
Examples are: int, char, bool, float, pointer.

Non-Primitive data structure:

Non-primitive data structures are user-defined data structures that are built using primitive data
types and can store multiple values.

Types of Non-Primitive Data Structures:

1. Homogeneous
Store data of the same type.

Examples:
Array, Linked List

2. Heterogeneous

Store data of different types.

Examples:
Structure (e.g., struct), Object

Non-Primitive Data Structures (Based on Structure)

Non-primitive data structures are divided into two types based on how data is organized:

1. Linear Data Structure

A type of linear data structure where elements are arranged in a linear order, one after
another(sequentially) , in contiguous or non-contiguous memory locations.

Examples: Array, Linked List, Stack, Queue

Linear data structure can be divided into two types:

1. Static
2. Dynamic

Static data structure are those whose size is stated during compile time, and can’t be shrink or
grow at run time.

Example: Array is the best example of static data structure.

Dynamic data structure is those whose size is not stated during compile time, and can grow or
shrink at run time.

Example: vector is the best example of dynamic data structure.

2. Non-Linear Data Structure

A type of non-primitive data structure in which data is stored in a hierarchical or network-like
structure.
Elements are not arranged in a sequential manner.

Examples: Tree, Graph

Basic operations of data structure:

1. Traversal

Traversal is the process of accessing each and every element of a data structure exactly once.

Example: Printing all elements of an array requires traversal.

2. Searching

Searching is the process of finding the location of a specific data item (or a set of items) in a data
structure based on a condition.

Examples:

 Finding the position of number 5 in an array

 Finding all ages greater than 18 in an array of student ages

3. Insertion

Insertion is the process of adding a new element to a data structure.

Example: Adding the record of a newly enrolled student into an array.

4. Deletion
Deletion is the process of removing an existing data item from a data structure.

Example: Deleting the record of a student who leaves the school.

5. Sorting

Sorting is the process of arranging data in ascending or descending order.

6. Merging

Merging is the process of combining the elements of two data structures into a single data
structure.

Example: Combining two sorted arrays into one sorted array.

7. Creation

Creation is the process of allocating memory for data elements. It can be done either at compile
time or run time.

Examples:

 Declaring an array of size 10 at compile time

 Creating a linked list node dynamically at run time using memory allocation functions like
malloc() or new

8. Selection

Selection is the process of choosing a particular data item (or items) from a data structure based
on a condition.

Example: Selecting the element 7 from a list of 10 elements using a condition in a loop.
9. Updating

Updating is the process of modifying an existing data item (or items) in a data structure.

Examples:

 Updating the value stored at index 3 of an array to 8

 Increasing the values of elements stored beyond index 4 by 3

10. Splitting

Splitting is the process of dividing a data structure into smaller subparts to make processing
easier and more efficient.

Example: Dividing a large array into smaller arrays for faster processing.

Algorithm
An algorithm is a step-by-step procedure or set of instructions used to solve a problem or
perform a task.

 It is not a program, but a logical solution to a problem.

 It is usually written in the form of pseudocode or represented using a flowchart.

Data Flow of an Algorithm

1. Problem

First, we identify a real-world problem for which we need to design a solution or write a
program.

2. Algorithm

A step-by-step solution to the problem is designed.

3. Input
After designing the algorithm, the required and desired inputs are provided.

4. Processing Unit

The input is processed according to the algorithm, and the processing unit produces the desired
output.

5. Output

The output is the final result produced after processing.

Why do we need algorithms?

 Scalability:
Algorithms help us break a big problem into smaller and easier parts, so the problem
becomes easy to understand and solve.
 Performance:
Algorithms allow us to solve problems in the most efficient way, giving good
performance in terms of both speed and memory/size.

Factors of an Algorithm

 Modularity:
A big problem is divided into smaller sub-problems, making it easier to understand and solve.
This is what algorithms do.
 Correctness:
An algorithm should produce the correct and desired output for the given input. This is called the
correctness of an algorithm.
 Maintainability:
A good algorithm should be simple and well-structured so it can be easily maintained and
updated in the future.
 Functionality:
An algorithm uses logical steps to solve real-world problems.
 Robustness:
A robust algorithm works properly even when unusual or wrong input is given.
 User-Friendly: A good algorithm is simple and easy for programmers to understand and use
 Extensibility: If any other algorithm designer or programmer wants to use your algorithm then it
should be extensible.

Importance of Algorithms
Theoretical Importance:
An algorithm must first be understood theoretically because solving a problem without
understanding it is not possible.
Example: In a water tank problem, we first need to understand the problem theoretically before
solving it.

Practical Importance:
Once we understand the problem theoretically, it is important to implement the algorithm
practically to solve it in real life or in a program.

Algorithm Analysis:
Algorithm can be analyzed in two ways: before implementation and after implementation.

i. Prior Analysis:
The analysis of an algorithm before implementing it in any programming language.

ii. Posterior Analysis:

The analysis of an algorithm after implementing it in a programming language.

ANALYSIS OF ALGORITHM

 Analysis of algorithms is a basic concept in computer science that is used to check the
performance of algorithms and programs.
 Efficiency is measured in terms of time and space.
 The term “analysis of algorithms” was introduced by Donald Knuth.
 It is used to estimate how an algorithm performs when the input size becomes very large.
 In simple words, algorithm analysis tells us how much time and memory an algorithm
will take to solve a problem.
 Time complexity means the running time of an algorithm based on input size.
 Space complexity means the amount of memory used by an algorithm based on input
size.

 Algorithms are evaluated based on time complexity, space complexity, and practical
efficiency when working with different types of data.
 Different algorithms can solve the same problem, but in different ways.
 For example, sorting a set of numbers can be done using different algorithms.
 The number of comparisons in each sorting algorithm may be different for the same
input.
 Because of this, the time complexity of algorithms can vary.
  We also measure the memory (space) required by each algorithm.
 After designing an algorithm, it is important to ensure that it gives the correct output for
every valid input.
 Therefore, the correctness of an algorithm must be proven.

Analysis of Algorithm (Simple Bullet Points)

 Analysis of an algorithm means checking how well it solves a problem in terms of time and
memory (space).
 It measures how much time an algorithm takes and how much memory it needs during execution.
 The main focus of algorithm analysis is usually performance (time efficiency).

Types of Analysis:

 Worst Case:
The maximum number of steps an algorithm takes to solve a problem.
 Best Case:
The minimum number of steps an algorithm takes to solve a problem.
 Average Case:
The average number of steps an algorithm takes to solve a problem.

Example: Finding the position of 5 in the following array or 7 elements:

Arr= |1|3|6|5|8|9|2|

 If 5 is at index 1, best case

 If 5 is at index 6, worst case
 If 5 is somewhere at the range of 0-5, average case

Example:

 Different sorting algorithms like Bubble Sort and Merge Sort behave differently.
 Bubble Sort does not use extra memory, but it takes more time.
 Merge Sort uses extra memory but is faster.
 So, in situations where memory is limited, Bubble Sort may be preferred even if it is slower.

Slide no.1 Ended

Chipter#1: Design and Analysis of Algorithm

Algorithm
An algorithm is a step-by-step solution to a problem.

 It is usually written in natural language.

Ways of Describing an Algorithm

i. Flowchart

A flowchart is a graphical representation of an algorithm using different shapes and arrows to

show the flow of steps.

ii. Pseudocode

Pseudocode is a programming-style description of an algorithm using keywords and structure.

 It is general and not tailored to any specific programming language.

 It can be converted into any programming language.
 It is not as strict as actual programming syntax.

Programming
Programming is the process of writing a set of instructions by following the rules and syntax of a
specific programming language to perform a specific task.

 It is the conversion of pseudocode or algorithms into actual code.

How a Program Works

Input

The program takes input from the user or another source.

Process

The program processes the input according to the instructions.

Output

The program produces the desired result or output.

Example
Algorithm

1. Start
2. Declare variable iii
3. Input value of iii
4. Check if i<10i < 10i<10
5. If true, display:
“The number you entered is less than 10”
6. Otherwise, display:
“The number is greater than or equal to 10”
7. Stop

Pseudocode

BEGIN

DECLARE i

INPUT i

IF i < 10 THEN
PRINT "The number you entered is less than 10"
ELSE
PRINT "The number is greater than or equal to 10"

END IF

END

Flow Chart
C++ Program

#include <iostream>
using namespace std;

int main()
{
 int i;

cin >> i;

if(i < 10)

{
cout << "The number you entered is less than 10" << endl;
}
else
{
cout << "The number is greater than or equal to 10" << endl;
}

return 0;
}

Ways of Analyzing Algorithm

There are two ways:
1. Experiential Analysis
2. Theoretical analysis

1. Experiential Analysis
Experimental analysis is the process of implementing an algorithm, running it with different
input sizes, and plotting the results on a graph to evaluate its performance.

Observation

 If the graph increases rapidly as the input size grows, the algorithm is likely to be inefficient.
 If the graph increases slowly as the input size grows, the algorithm is likely to be efficient.

Limitations of Experimental Analysis

 Time-consuming, since the algorithm must be implemented and tested.

 Results may vary depending on the hardware and software environment.
 To compare two algorithms fairly, both should be tested on the same device with the same
hardware and software specifications.

2. Theoretical Analysis
Theoretical analysis is the process of analyzing an algorithm without implementing or running
the program. Instead, it uses mathematical calculations to evaluate the algorithm based on the
input size (n).

Characteristics

 Uses the description (logic) of the algorithm instead of its implementation.

 Measures the running time as a function of the input size (n).
 Considers all possible input cases, such as Best Case and Worst Case.
 Does not depend on the hardware or software of the computer (assumes the RAM model).
 Uses mathematical analysis instead of experiments.

Observation

 If the input size (n) increases and the number of operations also increases at the same rate, it is
called Linear Growth (O(n)) and is generally considered efficient.
 If the input size (n) increases and the number of operations increase as the square of the input size
(n²), it is called Quadratic Growth (O(n²)) and is generally considered inefficient.
 If the input size (n) increases but the number of operations increase very slowly, it is called
Logarithmic Growth (O(log n)) and is considered very efficient.
 If the input size (n) increases but the number of operations remain the same, it is called Constant
Growth (O(1)) and is the most efficient.
Worst-Case, Best-Case, and Average-Case Analysis

Algorithm analysis measures how an algorithm performs for an input of size n.

1. Worst-Case Analysis

Definition:
The maximum amount of time an algorithm takes to solve a problem of input size n.

 Represents the slowest possible execution of the algorithm.

 Represented by: Big-O (O) notation.
 It is the standard method for analyzing algorithms.
 We usually analyze the worst case because it guarantees the maximum time an algorithm will
take.

2. Best-Case Analysis

Definition:
The minimum amount of time an algorithm takes to solve a problem of input size n.

 Represents the fastest possible execution of the algorithm.

 Represented by: Big-Omega (Ω) notation.
 It is less useful because it only describes the most favorable situation, which may not occur in
practice.

3. Average-Case Analysis

Definition:
The average amount of time an algorithm takes to solve a problem of input size n, considering
all possible inputs.

 Represents the expected running time of the algorithm.

 Represented by: Big-Theta (Θ) notation (when the average-case bound is known and tight).
 It is less commonly used than worst-case analysis because calculating the average running time
often requires assumptions about the input distribution and can be more difficult.
Running Time T(N)
T(N) = Time taken by an algorithm for an input of size N — measured by counting the total number of
primitive operations (basic steps) executed.

RAM Model:
We use the standard RAM model to count primitive operations where every basic operation costs 1 unit
regardless of type (add, multiply, divide, assign — all equal).

Example 1:
y=m*x+b

Operation Cost
m * x (multiply) 1
+ b (add) 1
y = (assign) 1
Total T(N) 3

Example 2:

Example 2:
c = 5 / 9 * (t - 32)

Operation Cost

t - 32 (subtract) 1

5 / 9 (divide) 1

× result (multiply) 1

c = (assign) 1

Total T(N) 4
Formula:

T(N) = Σ (cost of each statement) × (number of times it executes)

If a statement runs inside a loop of 100 iterations:
cost 1 × 100 times = 100

OR(in my way)
Time Complexity (T(N))
Definition

Time Complexity, denoted by T(N), is the amount of time an algorithm takes to execute for an
input of size N.

It is measured by counting the number of basic operations performed by the algorithm.

Assumption: Each basic operation has a cost of 1 unit.

Basic Operations
Basic operations include:

 Addition (+)
 Subtraction (-)
 Multiplication (*)
 Division (/)
 Assignment (=)
 Comparison (<, >, ==, etc.)

Each basic operation is assumed to take 1 unit of time.

Example
x+y-3
Operations:

 x + y → Cost = 1
 (x + y) - 3 → Cost = 1

Total Cost = 2

Formula
Time Complexity=∑(Cost of Statement×Number of Times it Executes)\boxed{\text{Time Complexity} =
\sum (\text{Cost of Statement} \times \text{Number of Times it
Executes})}Time Complexity=∑(Cost of Statement×Number of Times it Executes)

Simple Definition

Time Complexity is calculated by multiplying the cost of each statement by the number of times
it executes, and then adding the results for all statements.

Example 1

for(i = 0; i < n; i++)

{
sum = sum + i;
}
Statement Cost Executions

i=0 1 1

i<n 1 n+1

i++ 1 n

sum = sum + I 2 (addition + assignment) n

The total time complexity is found by adding the cost of each statement multiplied by the number of
times it executes.

Total Time Complexity

T(N)=1+(n+1) +n+2n

T(N)=4n+2
=O(n)

Example 2:

Example no.3:

Running time analysis

// Input: int A[N], array of N integers
// Output: Sum of all numbers in array A

int Sum(int A[], int N)

{
int s=0; ---------------------------------(1)
for (int i=0; i< N; i++) -------------------(1+(n+1) +n)
s = s + A[i]; ---------------------(2*n
return s; ----------------------------------(n)
}

Total Time Complexity Function:

T(N)= 1+1+(n+1)+n+(2n)+n
= 5n+3
= 5n+3
= O(n)

Order of Growth is: N, Linear

Notice that when N=10:
5N + 3 = 5(10) + 3 = 53 steps

N=100
5N+3=5(100) +3=503 steps

This is how RAM model work, and how we analyze algorithms; So the most optimized algorithm is one
that grow slowly as the number of input size N grow.

currentMax ← A[0] 2(1)

There are 2 operations in this statement:

1. Read the value at the 0th index of the array.
2. Assign that value to the currentMax variable.

Therefore, its cost is 2(1).

for i ← 1 to i < n do 1(1) + 1(n)

There are 2 operations in this statement:

1. Initialize i = 1, which executes only one time.
2. Compare i with n, which executes n times. The comparison continues until i becomes equal to or greater than n,
then the loop stops.
Therefore, its cost is 1(1) + 1(n).

if A[i] > currentMax then 2(n−1)

There are 2 operations:

1. Read the value of A[i].
2. Compare A[i] with currentMax.

This statement executes (n−1) times because the loop runs from i = 1 to i = n−1.

currentMax ← A[i] 2(n−1)

There are 2 operations:

1. Read the value of A[i].
2. Assign that value to currentMax.

In the worst case, this statement executes (n−1) times (when every new element is greater than the current
maximum).

i←i+1 2(n−1)

There are 2 operations:

1. Add 1 to i.
2. Assign the new value back to i.

This statement executes (n−1) times because i is incremented after every loop iteration.

return currentMax 1(1)

There is 1 operation:
Return the value stored in currentMax.

This statement executes only one time.

Total = 2 + (1 + n) + 2(n−1) + 2(n−1) + 2(n−1) + 1

= 7n − 2
Running Time (Statement Counting Method)

 To simplify the analysis, the running time is calculated based on each statement instead of
primitive operations.
 Each statement is assumed to take a constant amount of time, denoted by Ci.
 Different statements may have different constant times (C₁, C₂, C₃, ...) because they may contain
different numbers of primitive operations.

Example:

i = 1; Cost = C₁
i = i + 1; Cost = C₂

Both statements take constant time, but their constants may be different because i = i + 1
performs more work than i = 1.

Example: Simple If-Statement

Cost Times
if (n < 0) c1 1
val = -n c2 1
else
val = n; c3 1

Total Cost <= c1 + max(c2,c3)

Why max(c2, c3)?

Ans: Because this is an if-else statement, only one branch executes at a time while the other
branch is skipped. The skipped branch contributes 0 to the running time because it is not
executed. Since time complexity analysis usually considers the worst case, we take the branch
with the greater cost. Therefore, the total cost is:

Total Cost <= c1 + max(c2,c3)

where c₁ is the cost of evaluating the condition, and max(c₂, c₃) represents the cost of the
branch that takes the most time.
Example: Simple Loop
Cost Times
i = 1; c1 1
sum = 0; c2 1
while (i <= n) { c3 n+1
i = i + 1; c4 n
sum = sum + i; c5 n
}

Total Cost = c1 + c2 + (n+1)*c3 + n*c4 + n*c5

 The time required for this algorithm is proportional to n

Growth Rate (Order of Growth)

Growth Rate:
The way the number of operations performed by an algorithm increases as the input size (n)
increases is called the growth rate of that algorithm.

Instead of measuring the exact running time, we compare algorithms based on their growth rates.
An algorithm with a smaller growth rate performs fewer operations and is generally more
efficient for large input sizes.

How to Find the Growth Rate from T(n)T(n)T(n)

1. Keep only the leading (highest-order) term.

2. Ignore all lower-order terms.
3. Ignore the constant coefficient of the leading term.

Examples

 T(n)=n+5T(n) = n + 5T(n)=n+5 → Growth Rate = nnn → O(n)

 T(n)=n2+7T(n) = n^2 + 7T(n)=n2+7 → Growth Rate = n2n^2n2 → O(n²)
 T(n)=105n2+108nT(n) = 105n^2 + 108nT(n)=105n2+108n → Growth Rate = n2n^2n2 → O(n²)

Important Points

 The growth rate is not affected by:

o Constant coefficients (e.g., 105, 7, ½)
o Lower-order terms (e.g., nnn, 5, 100)
 The efficiency of algorithms is compared based on their growth rate not the exact time taken by
them, because in different machines the same algorithm can take different time.
The End of Chapter 3