Data Structures and Algorithms

(CoSc2042 )
Prerequisite: Fundamentals of Programming in C++ (CoSc2031)

CHAPTER ONE: INTRODUCTION TO DATA

STRUCTURE AND ALGORITHM

Compiled by: Kassawmar M.

February, 2026
1
 Outline
 Introduction
 Abstract Data Types
 Abstraction
 Algorithms
 Properties of an algorithm
 Complexity Analysis
 Formal Approach to Analysis
 Asymptotic Analysis
 Asymptotic Notation

2/10/2026 2
 Introduction
A program
 A set of instruction which 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.
 Therefore, a program is Data structures plus
Algorithm.

2/10/2026 3
What are Data Structures?
 Data structure is a storage that is used to store and organize
data.
 It is a way of arranging data on a computer so that it can be
accessed and updated efficiently.
 Depending on your requirement and project, it is important
to choose the right data structure for your project.
 For example, if you want to store data sequentially in the
memory, then you can go for the Array data structure.

Array data Structure Representation

 Data structure is the collection of data types arranged in a
specific order.
 Cont.…
• The first step to solve the problem is obtaining ones own
abstract view, or model of the problem.
• This process of modeling is called abstraction.

Abstraction

 The model defines an abstract view to the problem.

 The model should only focus on problem related stuff

2/10/2026 5
 Abstraction
 Abstraction is a process of classifying characteristics as
relevant and irrelevant for the particular purpose at hand
and ignoring the irrelevant ones.

 Example: model students of HU.

 Relevant:
Char Name[15];
Char ID[11];
Char Dept[20];
int Age, year;
 Non relevant
float height, weight;
2/10/2026 6
 Cont.…
 Using the model, a programmer tries to define the
properties of the problem.

 These properties include

 The data which are affected and
 The operations that are involved in the problem

 An entity with the properties just described is

called an abstract data type (ADT).

2/10/2026 7
 Abstract Data Types

 Is a specification that describes a dataset and the

operation on that data.
 Consists of data to be stored and operations
supported on them.
 The ADT specifies:
 What data is stored.
 What operations can be done on the data.
 Does not specify how to store or how to
implement the operation.
 Is independent of any programming language

2/10/2026 8
 Cont…
Example: ADT employees of an organization:
 This ADT stores employees with their relevant
attributes and discarding irrelevant attributes.
Relevant:- Name, ID, Sex, Age, Salary, Dep't, Address
Non Relevant :- weight, color, height
 This ADT supports insert, update operations.
 In Contrast a data structure is a language construct that
the programmer has defined in order to implement an
abstract data type.

 Data structures are used to model a problem.

2/10/2026 9
 Con’t…
 Based on the type of data store, there are two different kinds of
data structures.
 Primitive Data Structures are basic data structures provided
by programming languages to represent single values, such as
integers, floating-point numbers, characters, and Booleans.
 Non-Primitive Data Structures are higher-level data
structures that are built using primitive data types and provide
more complex and specialized operations.
◦ Some common examples of abstract data structures include
arrays, linked lists, stacks, queues, trees, and graphs.
 Basically, based on organize and process a very large amount of
data, data structures are divided into two categories:
◦ Linear data structure
◦ Non-linear data structure

10
Con’t…

11
 Con’t…
Linear data structures
 In linear data structures, the elements are arranged in
sequence one after the other, they are easy to implement.
 However, when the complexity of the program increases,
the linear data structures might not be the best choice
because of operational complexities.
Popular linear data structures are:
[Link] Data Structure
 In an array, elements in memory are arranged in
continuous memory.
 All the elements of an array are of the same type.
 And, the type of elements that can be stored in the form
of arrays is determined by the programming language.

An array with each element represented by an index

 Con’t…
ii. Stack Data Structure
 In stack data structure, elements are works in the LIFO principle.
That is, the last element stored in a stack will be removed first.

iii. Queue Data Structure

 Queue data structure works in the FIFO principle where first
element stored in the queue will be removed first.
 In a queue, addition and removal are performed from separate
ends.

iv. Linked List Data Structure

 In linked list data structure, data elements are connected
through a series of nodes. And, each node contains the data
items and address to the next node.

Linked list
 Con’t…
Nonlinear data structures
 Unlike linear data structures, elements in non-linear data structures are in
any sequence.
 Instead they are arranged in a hierarchical manner where one element will
be connected to one or more elements. Eg. graph and tree.
i. Graph Data Structure
 In graph data structure, each node is called vertex and each vertex is
connected to other vertices through edges.

Graph data structure example

[Link] Data Structure

 Similar to a graph, a tree is also a collection of vertices and edges. However,
in tree data structure, there can only be one path between two vertices.

Tree data Tree structure

Example
 Popular Tree based Data Structure
◦ Binary Tree, Binary Search Tree, AVL Tree, B-Tree, B+ Tree
 Linear Vs Non-linear Data Structures
Linear Data Structures Non Linear Data Structures

The data items are arranged in The data items are arranged in any
sequential order, one after the other. order (hierarchical manner).

All the items are present on the single The data items are present at different
layer. layers.

It can be traversed on a single run. That It requires multiple runs. That is, if we
is, if we start from the first element, we start from the first element it might not
can traverse all the elements be possible to traverse all the elements
sequentially in a single pass. in a single pass.

Different structures utilize memory in

The memory utilization is not efficient. different efficient ways depending on
the need.

The time complexity increase with the

Time complexity remains the same.
data size.

Example:Arrays, Stack, Queue Example:Tree, Graph

 Algorithm
 Is a concise specification of an operation for
solving a problem.

 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.

Inputs Algorithm Outputs

 An algorithm is a specification of a behavioral

process. It consists of a finite set of instructions
that govern behavior step-by-step.
2/10/2026 16
 Cont…
 Data structures model the static part of the world.
They are unchanging while the world is changing.
 In order to model the dynamic part of the world we
need to work with algorithms.

 Algorithms are the dynamic part of a program’s world

model.
 An algorithm transforms data structures from
one state to another state.

2/10/2026 17
 Cont…
 What is the purpose of algorithms in programs?
◦ Take values as input. Example: cin>>age;
◦ Change the values held by data structures.
Example: age=age+1;
◦ Change the organization of the data structure:
Example: Sort students by name
◦ Produce outputs:
 Example: Display student’s information
 The quality of a data structure is related to its ability to
successfully model the characteristics of the world
(problem).
 Similarly, the quality of an algorithm is related to its ability
to successfully simulate the changes in the world.

2/10/2026 18
 Cont…
 However, the quality of data structure and algorithms is
determined by their ability to work together well.
 Similarly, the quality of an algorithm is related to its ability
to successfully simulate the changes in the world.

 Generally speaking, correct data structures lead to simple

and efficient algorithms.

 And correct algorithms lead to accurate and efficient data

structures.
 An algorithm transforms data structures from one state to another
state in two ways:
◦ An algorithm may change the value held by a data structure
◦ An algorithm may change the data structure itself
2/10/2026 19
Properties of Algorithms
• Finiteness: Algorithm must complete after a finite number
of steps.
• 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.
• 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.
• Feasibility: It must be possible to perform each instruction.
• Correctness: It must compute correct answer for all
possible legal inputs.
• Language Independence: It must not depend on any one
programming language.

2/10/2026 20
 Cont…
• Completeness: It must solve the problem completely.
• Effectiveness: It must be possible to perform each step
exactly and in a finite amount of time.
• Efficiency: It must solve with the least amount of
computational resources such as time and space.
• Generality: Algorithm should be valid on all possible
inputs.
• Input/Output: There must be a specified number of input
values, and one or more result values.

2/10/2026 21
 Cont…
 The study of algorithms includes:
◦ How to Design algorithms (Describing algorithms)
◦ How to Analyze algorithms (In terms of time and memory
space)
◦ How to validate algorithms (for any input)
◦ How to express algorithms (Using programming language)
◦ How to test a program (debugging and maintaining)

2/10/2026 22
 Algorithm Analysis
 Algorithm analysis refers to the process of
determining how much computing time and
storage that algorithms will require.

 In other words, it’s a process of redacting the

resource requirement of algorithms in a given
environment.

 The efficiency of an algorithm is a measure of the

amount of resources consumed in solving a
problem of size n.
2/10/2026 23
 Cont…
 In order to solve a problem, there are many possible
algorithms.

 One has to be able to choose the best algorithm for

the problem at hand using some scientific method.

 To classify some data structures and algorithms as

good:

We need precise ways of analyzing them in terms of

resource requirement.

2/10/2026 24
 Cont…
 The main resources are:
• Running Time
• Memory Usage
• Communication Bandwidth
 Note: Running time is 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
• Theoretical

2/10/2026 25
 Empirical Algorithm Analysis
 It works based on the total running time of the program.
 It uses actual system clock time.
Example:
t1(Initial time before the program starts)
for(int i=0; i<=10; i++)
cout<<i;
t2 (final time after the execution of the program is finished)
Running time taken by the above algorithm (TotalTime) = t2-t1;
 It is difficult to determine efficiency of algorithms using this approach,
because clock-time can vary based on many factors. For
example:
a) Processor speed of the computer
b) Current processor load
c) Specific data for a particular run of the program (Input size, Input
properties)
d) Operating System
 Multitasking Vs Single tasking
 Internal structure 26
Theoretical Algorithm Analysis
 Determining the quantity of resources required using
mathematical concept.
 Analyze an algorithm according to the number of
basic operations (time units) required, rather than
according to an absolute amount of time involved.
 We use theoretical approach to determine the efficiency
of algorithm because:
• The number of operation will not vary under different
conditions.
• It helps us to have a meaningful measure that permits
comparison of algorithms independent of operating
platform.
• It helps to determine the complexity of algorithm.

2/10/2026 27
 Cont…
 Complexity Analysis 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.
 Two important ways to characterize the effectiveness of an
algorithm are its Space Complexity and Time Complexity.
◦ Time Complexity: Determine the approximate number of
operations required to solve a problem of size n. The limiting
behavior of time complexity as size increases is called
the Asymptotic Time Complexity.
◦ Space Complexity: Determine the approximate memory
required to solve a problem of size n. The limiting behavior of space
complexity as size increases is called the Asymptotic Space
Complexity.
o Asymptotic Complexity of an algorithm determines the size of
problems that can be solved by the algorithm.
28
 Cont…
• There is no generally accepted set of rules for algorithm
analysis.
• However, an exact count of operations is commonly used.
• To count the number of operations we can use the
following Analysis Rule.

Analysis Rules:
1. Assume an arbitrary time unit.
2. Execution of one of the following operations takes time 1.
 Assignment operation
 Single I/O operation
 Function return
 Single Boolean operation
 Single Arithmetic operation

2/10/2026 29
 Cont….
3. 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.
4. Loops- running time for a loop is equal to the running
time for the statements inside the loop * number of
iterations.
 The total running time of statements inside a group of nested
loops is the running time of the statements multiplied by the
product of the sizes of all the loops.
 For nested loops, analyze inside out.
 Always assume that the loop executes the maximum number of
iterations possible.
5. Running time of a function call is 1 for setup + the time
for any parameter calculations + the time required for
the execution of the function body.
2/10/2026 30
 Examples:
Time Units to Compute
1. int count(){ -------------------------------------------------
int k=0;
1 for the assignment statement: int k=0
cout<< “Enter an integer”;
1 for the output statement.
cin>>n;
1 for the input statement.
for (i=0;i<n;i++)
In the for loop:
k=k+1;
1 assignment, n+1 tests, and n increments.
return 0;
n loops of 2 units for an assignment, and an
} addition.
1 for the return statement.
T (n)= 1+1+1+(1+n+1+n)+2n+1 = 4n+6 = O(n)

31
2. int total(int n)
{
int sum=0;
for (int i=1;i<=n;i++)
sum=sum+1;
return sum;
}
Time Units to Compute
-------------------------------------------------
1 for the assignment statement: int sum=0
In the for loop:
1 assignment, n+1 tests, and n increments.
n loops of 2 units for an assignment, and an addition.
1 for the return statement.
-------------------------------------------------------------------
T (n)= 1+ (1+n+1+n)+2n+1 = 4n+4 = O(n)
32
3. void func()
{ Time Units to Compute
--------------------------------------------
int x=0;
1 for the first assignment statement: x=0;
int i=0; 1 for the second assignment statement: i=0;
int j=1; 1 for the third assignment statement: j=1;
1 for the output statement.
cout<< “Enter an Integer value”; 1 for the input statement.
cin>>n; In the first while loop:
n+1 tests
while (i<n){
n loops of 2 units for the two increment
x++; (addition) operations
i++; In the second while loop:
n tests
} n-1 increments
while (j<n) T (n)= 1+1+1+1+1+n+1+2n+n+n-1 =
{ 5n+5 = O(n)

j++;
} }
33
 Cont…
 Calculate the time complexity of the following program.

4). int sum(int n){

int s=0;
for(int i=1;i<=n;i++)
s=s+(i*i*i*i);
return s;
}
5). int sum(int n){
int sum=0;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
sum++;
}
34

2/10/2026 34
 Cont…
6) Calculate the time complexity and Big O value of the following program.
#include <iostream>
using namespace std;

int computeSquare(int n)
{
int sum = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
sum++;
return sum;
}
T(n)=1 (setup)+ parameter calc +Tbody
int main()
{
int n = 5;
int result = computeSquare(n);
cout << "Result = " << result << endl;
return 0;
}
35
 Cont…
7). Calculate the time complexity of the following program.

if (x > 0)
{
y = y + 1;
}
else
{
y = y + 1;
z = z + 2;
}

36

2/10/2026 36
Formal Approach to Analysis
 In the previous examples we have seen that analyzing
Loop statements is so complex. However, it can be
simplified by using some formal approach in which case
we can ignore initializations, loop control, and updates.
For Loops: Formally
 In general, a for loop translates to a summation. The
index and bounds of the summation are the same as the
index and bounds of the for loop.

 Suppose we count the number of additions that are

done. There is 1 addition per iteration of the loop,
hence N additions in total.
37
Consecutive Statements: Formally
 Add the running times of the separate blocks of your code.
 Nested Loops: Formally, nested for loops translate into
multiple summations, one for each For loop.

o Consecutive Statements: Formally, add the running times

of the separate blocks of your code.

38
Conditionals: Formally
 If (test) s1 else s2: Compute the maximum of the running
time for s1 and s2.

39
 Categories of Algorithm Analysis
 Algorithms may be examined under different situations to
correctly determine their efficiency for accurate
comparison.
 Algorithm analysis categories: according to efficiencies.
Best Case Analysis:
 Takes the smallest possible set of inputs.
 Causes execution of the fewest number of statements.
 Provides a lower bound on running time
 Assumes the input data are arranged in the most
advantageous order for the algorithm.

2/10/2026 40
 Cont…
 Computes the lower bound of T(n), where T(n)
is the complexity function.

Examples:
For sorting algorithm
 If the list is already sorted (data are arranged in
the required order).
For searching algorithm
 If the desired item is located at first accessed
position.

2/10/2026 41
 Cont…
Worst Case Analysis:
 Takes the worst possible set of inputs.
 Causes execution of the largest number of statements.
 Computes the upper bound of T(n) where T(n) is the
complexity function.
 Assumes the input data are arranged in the most
disadvantageous order for the algorithm.

Examples:
For sorting algorithms
 If the list is in opposite order.
For searching algorithms
 If the desired item is located at the last position or is
missing.

2/10/2026 42
 Cont…
Average Case Analysis:
 Determine the average of the running time overall
permutation of input data.
 Takes an average set of inputs.
 It causes average number of executions.
 Computes the optimal bound of T(n) where T(n) is the
complexity function.
Examples:
o While sorting, considering any arrangement (order of
input data).
o While searching, if the desired item is located at any
location or is missing.
 Average case analysis is often difficult to determine and define.
 If situations are in their best case, no need to develop
algorithms because data arrangements are in the best
situation.
 We are interested in the worst case time since it provides a
bound for all input-this is called the “Big-Oh” estimate.
2/10/2026 43
 Asymptotic Notations
 Asymptotic Analysis 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.
 Asymptotic notation is a shorthand way to represent the
time complexity.
 Asymptotic Analysis makes use of
◦ O (Big-Oh) notation
◦  (Omega) notation
◦  (Theta) notation
◦ o (little-o) and
◦  (little-omega) notations in performance analysis and
characterizing the complexity of an algorithm.
2/10/2026 44
 Types of Asymptotic Notations
1. Big-Oh Notation
 Definition: We say f(n)=O(g(n)), if there are positive
constants no and c, such that to the right of no, the value
of f(n) always lies on or below c.g(n).
 As n increases f(n) grows no faster than g(n).
 It’s only concerned with what happens for very large
values of n.
 Describes the worst case analysis.
 Gives an upper bound for a function to within a
constant factor.

2/10/2026 45
 Cont…
 Definition: Let f(n) and g(n) be two non-negative functions.

2/10/2026 46
 Cont..
Question-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 there exist

constants c and k such that f(n)<=c.g(n) for all n>=k.
10n+5<=c.n ==> for all n>=k
let c=15, then show that 10n+5<=15n
5<=5n or 1<=n
So, f(n)=10n+5<=15.g(n) for all n>=1
(c=15, k=1), there exist two constants that satisfy the above
constraints.
f(n) = O(n)

2/10/2026 47
Cont…

2/10/2026 48
 Cont..
2. Omega() - notation: The Omega notation is used to
represent the lower bound of algorithm’s running time.
◦ Used to represent the amount of time the algorithm
takes on the smallest possible set of inputs-“Best case”.

2/10/2026
49
 Cont..
3. Theta () notation: Using theta notation we can give
average amount of time taken by the algorithm to complete.
◦ To represent the amount of time the algorithm takes on an
average set of inputs- “Average case”.

2/10/2026 50
 Cont…
4. Little-oh Notation
 Definition: We say f(n)=o(g(n)), if there are positive
constants no and c such that to the right of no, the
value of f(n) lies below c.g(n).
 As n increases, g(n) grows strictly faster than f(n).
 f(n) grows strictly slower than g(n) asymptotically.
 Describes the worst case analysis.
 Denotes an upper bound that is not asymptotically
tight.
 Big O-Notation denotes an upper bound that may or
may not be asymptotically tight.

2/10/2026 51
 Cont…
5. Little-Omega () notation
 Definition: We write f(n)=(g(n)), if there are
positive constants no and c such that to the right of
no, the value of f(n) always lies above c.g(n).
◦ As n increases f(n) grows strictly faster than g(n).
◦ Describes the best case analysis.
 Denotes a lower bound that is not asymptotically
tight.
 Big -Notation denotes a lower bound that may or
may not be asymptotically tight.

2/10/2026 52
2/10/2026 53