Chapter One

Introduction

7/16/2025 1
Introduction to Data Structures and Algorithms
Analysis
• A program is written in order to solve a problem.
• A solution to a problem actually consists of two things:
– A way to organize the data
– Sequence of steps to solve the problem
• The way data are organized in a computers memory is
said to be Data Structure.
• The sequence of computational steps to solve a problem
is said to be an algorithm.
• A program is nothing but data structures plus algorithms.

7/16/2025 2
 Algorithms
• An algorithm is a well-defined computational
procedure that takes some value or a set of values as
input and produces some value or a set of values as
output.
• Data structures model the static part of the world.
• Algorithm model the dynamic part of the world.
• An algorithm transforms data structures from one state
to another state in two ways:
– It may change the value held by a data structure
– It may change the data structure itself

7/16/2025 3
• The quality of a data structure is related to its ability to
successfully model the characteristics of the world.
• the quality of an algorithm is related to its ability to
successfully simulate the changes in the world.
• Independent of any particular world model, the quality
of data structure and algorithms is determined by their
ability to work together well.
• Correct data structures lead to simple and efficient
algorithms and correct algorithms lead to accurate and
efficient data structures.

7/16/2025 4
• Properties of an algorithm
– Finiteness: Algorithm must complete after a finite
number of steps.
• Example:
– Consider an algorithm that calculates the sum of the first n natural
numbers:
1. Initialize sum = 0.
2. For i from 1 to n:
a. sum = sum + i
3. Return sum.
• This algorithm will complete in n steps, which is finite.
• Example of Infiniteness
1. Input a positive integer N
2. While N is not equal to 1:
a, If N is even, set N = N / 2
b. If N is odd, set N = 3 * N + 1
7/17/2025 3. Return "Done" 5
 – Definiteness: Each step must be clearly defined, having
one and only one interpretation.
• At each point in computation, one should be able to tell
exactly what happens next.
• Example:
– In a sorting algorithm like Bubble Sort:
1. Compare adjacent elements of the array.
2. If the first element is greater than the second, swap them.
– Each instruction is clear and leaves no ambiguity about what
should happen next.

7/16/2025 6
 – Sequence: Each step must have a unique defined
preceding and succeeding step.
• The first step (start step) and last step (halt step) must be
clearly noted.
• Example:
– For a simple algorithm to find the maximum of two numbers:
1. Start
2. Input numbers A and B.
3. If A > B, then max = A.
4. Else, max = B.
5. Output max.
6. Stop
– Here, the start and stop steps are clearly defined, and each step
follows logically.

7/16/2025 7
 – Feasibility: It must be possible to perform each
instruction.
• Example:
– An algorithm for multiplying two numbers:
1. Input A and B.
2. Set product = 0.
3. Repeat B times:
a. product = product + A.
4. Return product.
– Each step is feasible with basic operations available in any
programming environment.
• Example of Infeasible algorithm
1. Input an encrypted message.
2. Try every possible key until the correct one is found.
3. Return the decrypted message.
• If the encryption uses 256-bit AES, there are 2256 possible keys, which
take trillions of year to test all keys using the world’s fastest
7/16/2025 supercomputers. 8
 – Correctness: It must compute correct answer for all
possible legal inputs.
• Example:
– An algorithm for division:
1. Input A (numerator) and B (denominator).
2. If B = 0, return "undefined".
3. Else, result = A / B.
4. Return result.
– This algorithm correctly handles all legal inputs, including the case
where division by zero is attempted.

7/16/2025 9
 – Language Independence: It must not depend on any one
programming language.
• Example:
– The algorithm for finding the factorial can be described in
pseudocode:
1. Input n.
2. If n = 0, return 1.
3. Else, return n * factorial(n - 1).
– This can be implemented in any programming language without
changing its logic.

7/16/2025 10
 – Completeness: It must solve the problem completely.
• Example:
– An algorithm for solving a quadratic equation:
1. Input coefficients a, b, c.
2. Calculate the discriminant D = b^2 - 4ac.
3. If D > 0, return two real roots.
4. If D = 0, return one real root.
5. If D < 0, return "No real roots".
– This algorithm covers all possible cases for quadratic equations.

7/16/2025 11
 – Effectiveness: It must be possible to perform each step
exactly and in a finite amount of time.
• Example:
– Consider an algorithm that checks if a number is even:
1. Input n.
2. If n mod 2 = 0, return "even".
3. Else, return "odd".
– Each operation (modulus and comparison) can be performed in a
finite time.

7/16/2025 12
 – Efficiency: It must solve with the least amount of
computational resources such as time and space.
• Example:
– Using a binary search algorithm to find an element in a sorted
array is more efficient than a linear search:
1. Input sorted array and target.
2. Set low = 0, high = length(array) - 1.
3. While low <= high:
a. mid = (low + high) / 2.
b. If array[mid] = target, return mid.
c. If array[mid] < target, low = mid + 1.
d. Else, high = mid - 1.
– Binary search operates in O(log n) time, which is more efficient
than O(n) for a linear search.

7/16/2025 13
 – Generality: Algorithm should be valid on all possible
inputs.
• Example:
– An algorithm for finding the greatest common divisor (GCD) of
two numbers:
1. Input A and B.
2. While B ≠ 0:
a. temp = B.
b. B = A mod B.
c. A = temp.
3. Return A.
– This algorithm works for any pair of non-negative integers.

7/16/2025 14
 – Input/Output: There must be a specified number of
input values, and one or more result values.
• Example:
– An algorithm to calculate the average:
1. Input n (number of elements).
2. Input array of size n.
3. Sum = 0.
4. For each element in the array:
a. Sum = Sum + element.
5. Return Sum / n.
– This algorithm specifies the number of inputs (n elements) and
produces one output (the average).

7/16/2025 15
• Algorithm Analysis Concepts
– Algorithm analysis
• refers to the process of determining the amount of
computing time and storage space required by different
algorithms.
• Is a process of predicting the resource requirement of
algorithms in a given environment.
– To classify some data structures and algorithms as good,
we need precise ways of analyzing them in terms of
resource requirement.
– The main resources are:
• Running Time
• Memory Usage
• Communication Bandwidth
7/16/2025 16
 – Running time is usually treated as the most important
• since computational time is the most precious resource in
most problem domains.
– There are two approaches to measure the efficiency of
algorithms:
• Empirical: Programming competing algorithms and trying
them on different instances.
• Theoretical: Determining the quantity of resources
required mathematically (Execution time, memory space,
etc.) needed by each algorithm.
– it is difficult to use actual clock-time as a consistent
measure of an algorithm's efficiency,
• because clock-time can vary significantly depending on
various factors, making it an inconsistent metric for
comparing algorithms.
7/16/2025 17
 – For example,
• Specific processor speed
• Current processor load
• Specific data for a particular run of the program
– Input Size
– Input Properties
• Operating Environment
– Hence, we can analyze an algorithm according to the
number of operations required, rather than according to
an absolute amount of time involved.

7/16/2025 18
• Complexity Analysis
– It is the systematic study of the cost of computation,
measured either in time units or in operations performed,
or in the amount of storage space required.
– Goal: to have a meaningful measure that permits
comparison of algorithms independent of operating
platform.
– Things to consider:
• Time Complexity: Determine the approximate number of
operations required to solve a problem of size n.
• Space Complexity: Determine the approximate memory
required to solve a problem of size n.

7/16/2025 19
 – Complexity analysis involves two distinct phases:
• Algorithm Analysis: - Analysis of the algorithm or data
structure to produce a function T(n) that describes the
algorithm in terms of the operations performed in order to
measure the complexity of the algorithm.
• Order of Magnitude Analysis: Analysis of the function
T(n) to determine the general complexity category to
which it belongs.
– There is no generally accepted set of rules for algorithm
analysis.
• However, an exact count of operations is commonly used.
– Algorithm Efficiency is used to describe properties of an
algorithm relating to how much of various types of
resources it consumes.
• (Time and space are the most frequently encountered
7/16/2025
resources). 20
 – At the design stage of solving a particular problem, there
are two conflicting goals.
– These goals reflect the trade-offs between software
engineering principles and algorithmic efficiency.
– These goals are:
• To design an algorithm that is easy to understand, code,
and design.
– This goal is the concern of software engineering.
• To design an algorithm that makes efficient use of
computer resources such as CPU and memory (In terms of
hardware).
– This is a factor of time and space and results a quantitative
analysis of algorithm.
– This goal is the concern of data structure and algorithm
analysis.

7/16/2025 21
 – Trade-off: The two goals often conflict, and the
choice depends on the problem size, performance
requirements, and development context.

7/16/2025 22
• Qualitative Analysis Vs. Quantitative Analysis
– Qualitative Analysis
• focuses on the non-measurable qualities of an algorithm.
• These are subjective but critical for ensuring that the
algorithm is practical, maintainable, and reliable.
• A good algorithm should have the following qualities:
– Simple but powerful
– Easily understandable
– Easily modifiable
– Correct in all cases
– Well documented
» Internal Documentation (Comments)
» External Documentation (User manual)
– Modular

7/16/2025 23
 – Quantitative Analysis
• Focuses on the measurable efficiency of an algorithm,
• primarily in terms of time complexity (how fast it runs)
and space complexity (how much memory it uses).
• It also identifies avoidable inefficiencies that can degrade
performance.
• Some avoidable causes of algorithm inefficiencies are:
– Redundant Computation
– Late Termination of Loops
– Referencing an array element

7/16/2025 24
 • Redundant Computation
const int a = 10;
const int n = 1000;
int main(){
int x = 0, y;
for(I = 0; I < n; I++) {
x = x + 3;
y = a * a * x;
}
cout<<“Y = “<<y;
}

7/16/2025 25
 • Solution for Redundant Computation
int z = a * a;
for (int I = 0; I < n; I++) {
x = x + 3;
y = z * x;
}
• Trade Off: Time and Space
– Gaining one resource (efficiency) at the expense of
losing another (efficiency).
– In the above example, we “took” an additional space
for the variable z in order to gain speed of execution.

7/16/2025 26
 • Late Termination of Loop
const int n = 1000;
int search(int arr[], int key){
int flag = 0, J;
for(J = 0; J< n; J++)
if(x[J] = = key)
flag = 1;
return flag;
}
Solution
for (J = 0; J < n; J++)
if (x[J] = = key) {
flag = 1;
break;
}

7/16/2025 27
 • Referencing an Array Element
const int n = 1000;
const int a = 900;
int main( ) {
int y[n], x = 0,J;
for (J = 0; J < n; J++)
y[J] = J;
for (J = 0; J < n; J++)
x = x + y[a] + J;
cout<<< x;
}
• Referencing an array element costs CPU time.
• Solution
int v = y[a];
for (J = 0; J < n; J++)
x = x + v + J;
7/16/2025 28
 • Trade Off: Time and Space
– Gaining one resource (efficiency) at the expense of
losing another (efficiency).
– In the above example, we “took” an additional space
for the variable v in order to gain speed of execution.

7/16/2025 29
• Analysis Rules:
We assume an arbitrary time unit
1. Execution of one of the following operations takes 1
time unit:
• Assignment Operation
• Single Input/Output Operation
• Single Boolean Operations
• Single Arithmetic Operations
• Function Return
2. Running time of a selection statement (if, switch) is
• the time for the condition evaluation + the maximum of the
running times for the individual clauses in the selection.

7/16/2025 30
 3. Running time for a loop is
• the running time for the statements inside the loop *
number of iterations.
4. The total running time of a statement inside a group of
nested loops is the running time of the statements
multiplied by the product of the sizes of all the loops.
5. The running time of a function call can be thought of as
the sum of three components:
• Setup Time or function calling (1 unit):
• Parameter Calculation Time: The time required to
compute the values of the parameters passed to the
function.
• Execution Time of the Function Body: The time required
to execute the statements inside the function.

7/16/2025 31
 Examples
1. int count() {
int k=0,i,j,n ;
cout<< “Enter an integer”;
cin>>n;
k = i + j * n;
return 0;
}

7/16/2025 32
 – Time Units to Compute
• 1 for the assignment statement: int k=0
• 1 for the output statement.
• 1 for the input statement.
• 3 for the arithmetic and assignment statements
• 1 for the return statement.
– T (n) = 1+1+1+3+1
=7

7/16/2025 33
2. for (i = 0; i < n; i++)
k = k+1;
cout<<k;
– Time Units to Compute
• 1 for the initialization statement (i = 0)
• n + 1 for the boolean statement (i < n).
• n for the increment statement (i++).
• 2n for the arithmetic and assignment statement (k = k + 1)
• 1 for the output statement.
– T (n) = 1+ n + 1 + n + 2n + 1
= 4n + 3

7/16/2025 34
 3. int add(int a, int b) {
int result = a + b;
return result;
}
int main() {
int x, y;
cout << "Enter the value of x: ";
cin >> x;
cout << "Enter the value of y: ";
cin >> y;
int sum = add(x, y);
cout << "Sum: " << sum << endl;
return 0;
}

7/16/2025 35
 – Time Units to Compute
• 2 time units for the output statements
• 1 time unit for the function call statement.
• 2 time units for the input statements
• 2 time units for the parameter calculation.
• 2 time units for Execution time of the function add():
• 1 time unit for the return statement
• 1 time unit for the assignment statement (int sum = )
• 3 time units for the output statement
• 1 for the return statement.
– T (n) = 2 + 1 + 2 + 2 + 2 + 1 + 1 + 3 + 1
= 15

7/16/2025 36
4. for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(i < j){
k = k + i;
else if (i > j)
k += j;
else {
k = j + I;
cout<<“Thank you”;
}
}
}

7/16/2025 37
 – Formal Approach to Analysis
• Loops
– a loop translates to a summation.
– The index and bounds of the summation are the same as the index
and bounds of the for loop.
for (int i = 1; i <= N; i++)
sum = sum+i;

7/16/2025 38
 • Nested Loops:
– Nested for loops translate into multiple summations, one for each
for loop.
for (int i = 1; i <= N; i++)
for (int j = 1; j <= M; j++)
sum = sum+i+j;

• Consecutive Statements:
for (int i = 1; i <= N; i++)
sum = sum+i;
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++)
sum = sum+i+j;

7/16/2025 39
 • Conditionals:
if (test == 1)
for (int i = 1; i <= N; i++)
sum = sum+i;
else
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++)
sum = sum+i+j;

7/16/2025 40
 Measures of Times
• In order to determine the running time of an algorithm it
is possible to define three functions Tbest(n), Tavg(n) and
Tworst(n) as the best, the average and the worst case
running time of the algorithm respectively.
• Average Case (Tavg): The amount of time the
algorithm takes on an "average" set of inputs.
• Worst Case (Tworst): The amount of time the
algorithm takes on the worst possible set of inputs.
• Best Case (Tbest): The amount of time the algorithm
takes on the smallest possible set of inputs.
• We are interested in the worst-case time, since it
provides a bound for all input – this is called the “Big-
Oh” estimate.
7/16/2025 41
 Asymptotic Analysis
• It is concerned with how the running time of an
algorithm increases with the size of the input in the
limit, as the size of the input increases without bound.
• There are five notations used to describe a running time
function. These are:
– Big-Oh Notation (O)
– Big-Omega Notation ()
– Theta Notation ()
– Little-o Notation (o)
– Little-Omega Notation ()

7/16/2025 42
• The Big-Oh Notation
– Big-Oh notation is a way of comparing algorithms and
– is used for computing the complexity of algorithms;
• i.e., the amount of time that it takes for computer program
to run.
– It’s only concerned with what happens for a very large
value of n.
– Therefore, only the largest term in the expression
(function) is needed.
– For example, if the number of operations in an algorithm
is n2 – n, n is insignificant compared to n2 for large values
of n.
– Hence the n term is ignored.
– Big-Oh is mainly concerned with large values of n.
7/16/2025 43
• Formal Definition: f (n) = O(g(n)) if there exist c, k ∊
ℛ+ such that for all n ≥ k, f (n) ≤ c.g (n).
• Examples: The following points are facts that you can
use for Big-Oh problems:
– 1<= n for all n >= 1
– n <= n2 for all n >= 1
– 2n <= n! for all n >= 4
– log2n <= n for all n >= 2
– n <= nlog2 n for all n >= 2

7/16/2025 44
 1. f(n) = 10n + 5 and g(n) = n.
• Show that f(n) is O(g(n)).
• To show that f(n) is O(g(n)) we must show that constants c
and k such that f(n) <= c.g(n) for all n >= k
• Or 10n + 5 <= c.n for all n >= k
• Try c = 15. Then we need to show that 10n + 5 <= 15n
• Solving for n we get: 5 < 5n or 1 <= n.
• So f(n) =10n + 5 <= 15.g(n) for all n >= 1. (c = 15, k = 1).

7/16/2025 45
 2. f(n) = 3n2 + 4n + 1. Show that f(n) = O(n2 ).
• 4n <= 4n2 for all n >= 1 and 1 <= n2 for all n >= 1
• 3n2 + 4n+1 <= 3n2 + 4n2 + n2 for all n >= 1
• <= 8n2 for all n >= 1
• So we have shown that f(n) <= 8n2 for all n >= 1
• Therefore, f (n) is O(n2 ) (c = 8, k = 1)

7/16/2025 46
• Typical Orders

• Big-O expresses an upper bound on the growth rate of a

7/16/2025 48