Chapter 1

Introduction to Data Structures and Algorithm Analysis

Introduction:

Data structures are the fundamental building blocks of computer

programming. They define how data is organized, stored, and manipulated
within a program.
A 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.
A data structure is not only used for organizing the data. It is also used for
processing, retrieving, and storing data.
Data Structures together with Algorithms

Data structures and algorithms (DSA) go hand in hand.

DSA is about finding efficient ways to store and retrieve data, to perform
operations on data, and to solve specific problems.

By understanding DSA, you can:

 Decide which data structure or algorithm is best for a given situation.

 Make programs that run faster or use less memory.
 Understand how to approach complex problems and solve them in a
systematic way.

Need of Data Structure:

Data Structures and Algorithms (DSA) are used in virtually every software
system, from operating systems to web applications:

 For managing large amounts of data, such as in a social network or a search

engine.
 For scheduling tasks, to decide which task a computer should do first.
 For planning routes, like in a GPS system to find the shortest path from A to
B.
 For optimizing processes, such as arranging tasks so they can be completed as
quickly as possible.
 For solving complex problems: From finding the best way to pack a truck to
making a computer 'learn' from data.

Definitions - Data and information, Data type

Data
Data is raw, unorganized, unprocessed information.
E.g., the information collected for writing a research paper is data until it is
presented in an organized manner

Information

Information is the processed, organized data that is beneficial in providing

useful knowledge.
For eg., the data compiled in an organized way in a research paper provides
information about a particular concept/ topic.

Data type:

A data type defines the type of value stored in a variable. This decides the type
of operations performed and functions called on these values. Whereas, a data
structure is a collection of similar or different types of data, which is used to
organize and manipulate data in a program.

Data object and ADT

Data Object:
A data object is a structure for describing a data entity by grouping a set of
related fields. For example, a supermarket Online orders application might
contain an Customer data object. As seen in the following image,
the Customer data object includes fields that describe the supermarket's
customer, such as First name, Last name, Full name, Email, and Phone
ADT :

Data types such as int, float, double, long, etc. are considered to be in-built
data types and we can perform basic operations with them such as addition,
subtraction, division, multiplication, etc.
There might be a situation when we need operations for our user-defined data
type which have to be defined. These operations can be defined only as and
when we require them. So, in order to simplify the process of solving
problems, we can create data structures along with their operations, and such
data structures that are not in-built are known as Abstract Data Type (ADT).

An Abstract Data Type (ADT) is a programming concept that defines a high-

level view of a data structure, without specifying the implementation details. In
other words, it is a blueprint for creating a data structure that defines the
behaviour and interface of the structure, without specifying how it is
implemented.
Classification of Data Structure:

1. Linear Data Structure : Data structure in which data elements are arranged
sequentially or linearly, where each element is attached to its previous and
next adjacent elements, is called a linear data structure.

Example: Array, Stack, Queue, Linked List, etc.

2. Static Data Structure: Static data structure has a fixed memory size. It is
easier to access the elements in a static data structure.
Example: array.

3. Dynamic Data Structure: In dynamic data structure, the size is not fixed.
It can be randomly updated during the runtime which may be considered
efficient concerning the memory (space) complexity of the code.
Example: Queue, Stack, etc.

4. Non-Linear Data Structure: Data structures where data elements are not
placed sequentially or linearly are called non-linear data structures. In a
non-linear data structure, we can’t traverse all the elements in a single run
only.
Examples: Trees and Graphs.
Algorithm Analysis
The algorithm can be analyzed in two levels, i.e., first is before creating
the algorithm, and second is after creating the algorithm. The following
are the two analysis of an algorithm:

o Priori Analysis: Here, priori analysis is the theoretical analysis of an

algorithm which is done before implementing the algorithm. Various
factors can be considered before implementing the algorithm like
processor speed, which has no effect on the implementation part.
o Posterior Analysis: Here, posterior analysis is a practical analysis of an
algorithm. The practical analysis is achieved by implementing the
algorithm using any programming language. This analysis basically
evaluate that how much running time and space taken by the algorithm.

2.1 Space and time complexity

The performance of the algorithm can be measured in two factors:

o Time complexity: The time complexity of an algorithm is the amount of

time required to complete the execution. The time complexity of an
algorithm is denoted by the big O notation. Here, big O notation is the
asymptotic notation to represent the time complexity. The time
complexity is mainly calculated by counting the number of steps to finish
the execution. Let's understand the time complexity through an example.

sum=0;
// Suppose we have to calculate the sum of n numbers.
for i=1 to n
sum=sum+i;
// when the loop ends then sum holds the sum of the n numbers
return sum;

In the above code, the time complexity of the loop statement will be atleast n,
and if the value of n increases, then the time complexity also increases. While
the complexity of the code, i.e., return sum will be constant as its value is not
dependent on the value of n and will provide the result in one step only. We
generally consider the worst-time complexity as it is the maximum time taken
for any given input size.
 o Space complexity: An algorithm's space complexity is the amount of
space required to solve a problem and produce an output. Similar to the
time complexity, space complexity is also expressed in big O notation.

For an algorithm, the space is required for the following purposes:

1. To store program instructions
2. To store constant values
3. To store variable values
4. To track the function calls, jumping statements, etc.

Auxiliary space: The extra space required by the algorithm, excluding the input
size, is known as an auxiliary space. The space complexity considers both the
spaces, i.e., auxiliary space, and space used by the input.

So,

Space complexity = Auxiliary space + Input size.

2.2 Best, Worst, Average case analysis:

Types of Algorithm Analysis:
1) Best case
2) Worst case
3) Average case
Best case: Define the input for which algorithm takes less time or minimum
time. In the best case calculate the lower bound of an algorithm. Example: In
the linear search when search data is present at the first location of large data
then the best case occurs.
Worst Case: Define the input for which algorithm takes a long time or
maximum time. In the worst calculate the upper bound of an algorithm.
Example: In the linear search when search data is not present at all then the
worst case occurs.
Average case: In the average case take all random inputs and calculate the
computation time for all inputs and then we divide it by the total number of
inputs.
 Average case = all random case time / total no of case

2.3 Asymptotic notations (Big O, Omega Ω, Theta )

2.3 Asymptotic Notations

The commonly used asymptotic notations used for calculating the running time
complexity of an algorithm is given below:

1. Big oh Notation (?)

2. Omega Notation (Ω)
3. Theta Notation (θ)

Big oh Notation (O)

 Big O notation is an asymptotic notation that measures the performance
of an algorithm by simply providing the order of growth of the function.
 This notation provides an upper bound on a function which ensures that
the function never grows faster than the upper bound. So, it gives the
least upper bound on a function so that the function never grows faster
than this upper bound.
 It is the formal way to express the upper boundary of an algorithm
running time. It measures the worst case of time complexity or the
algorithm's longest amount of time to complete its operation.
Omega Notation (Ω)
 It basically describes the best-case scenario which is opposite to the big o
notation.
 It is the formal way to represent the lower bound of an algorithm's
running time. It measures the best amount of time an algorithm can
possibly take to complete or the best-case time complexity.
 It determines what the fastest time that an algorithm can run is.
 If we required that an algorithm takes at least certain amount of time
without using an upper bound, we use big- Ω notation i.e. the Greek letter
"omega".
Theta Notation (θ)
 The theta notation mainly describes the average case scenarios.
 It represents the realistic time complexity of an algorithm. Every time, an
algorithm does not perform worst or best, in real-world problems,
algorithms mainly fluctuate between the worst-case and best-case, and
this gives us the average case of the algorithm.
 Big theta is mainly used when the value of worst-case and the best-case is
same.
 It is the formal way to express both the upper bound and lower bound of
an algorithm running time.
Examples
Q1. Imagine a classroom of 100 students in which you gave your pen to
one person. You have to find that pen without knowing to whom you
gave it.

O(n2): You go and ask the first person in the class if he has the pen. Also,
you ask this person about the other 99 people in the classroom if they
have that pen and so on,
This is what we call O(n2).
O(n): Going and asking each student individually is O(N).
O(log n): Now I divide the class into two groups, then ask: “Is it on the
left side, or the right side of the classroom?” Then I take that group and
divide it into two and ask again, and so on. Repeat the process till you are
left with one student who has your pen. This is what you mean by O(log
n).
 The O(n2) searches if only one student knows on which student the
pen is hidden.
 The O(n) if one student had the pen and only they knew it.
 The O(log n) search if all the students knew, but would only tell me if
I guessed the right side.

#include <stdio.h>

int main()
{
printf("Hello World");
return 0;
}

Time Complexity: In the above code “Hello World” is printed only

once on the screen.
So, the time complexity is constant: O(1)
Auxiliary Space: O(1)

Example 2

#include <stdio.h>
void main()
{
int i, n = 8;
for (i = 1; i <= n; i++) {
printf("Hello World !!!\n");
}
}

Time Complexity: In the above code “Hello World !!!” is printed

only n times on the screen, as the value of n can change.
So, the time complexity is linear: O(n) i.e. every time, a linear
amount of time is required to execute code.
Auxiliary Space: O(1)
 Example 3
#include <stdio.h>
void main()
{
int i, n = 8;
for (i = 1; i <= n; i=i*2) {
printf("Hello World !!!\n");
}
}
Time Complexity: O(log2(n))
Auxiliary Space: O(1)

If n=25
2raised to 0 =1
21 = 2
22=4
23=8
24=16
25=32

Example 4
Pseudocode : list_Sum(A, n)
{
total =0 // cost=1 no of times=1
for i=0 to n-1 // cost=2 no of times=n+1 (+1 for the end
false condition)
sum = sum + A[i] // cost=2 no of times=n
return sum // cost=1 no of times=1
}

Tsum=1 + 2 * (n+1) + 2 * n + 1 = 4n + 4 =C1 * n + C2 = O(n)

Therefore, the time complexity of the above code is O(n)
Example 5

int count = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < i; j++)
count++;
Lets see how many times count++ will run.

When 𝑖=0, it will run 0 times.

When 𝑖=1, it will run 1 times.
When 𝑖=2, it will run 2 times and so on.

will be 𝑂(𝑁2)
Total number of times count++ will run is 0+1+2+...+(𝑁−1)=𝑁∗(𝑁−1)2. So the time complexity

Time Complexity: O(N)

Auxiliary Space: O(1)

Chapter 2
 Unit II Array as a Data Structure
1. ADT of array, Operations
2. 2. Array applications - Searching
3. 3. Linear search
4. 4. Binary Search
5. 5. Sorting Terminology- Internal, External, Stable, In-place
Sorting
6. 6. Sorting Algorithms
7. 7. Bubble Sort, Insertion Sort, Selection Sort
8. 8. Divide and Conquer strategy: Merge Sort, Quick Sort.

ADT of array, Operations

Abstract Data type (ADT) is a type (or class) for objects whose behavior is
defined by a set of values and a set of operations. The definition of ADT only
mentions what operations are to be performed but not how these operations will
be implemented. It does not specify how data will be organized in memory and
what algorithms will be used for implementing the operations. It is called
“abstract” because it gives an implementation-independent view.
The process of providing only the essentials and hiding the details is known as
abstraction.
The user of data type does not need to know how that data type is implemented,
for example, we have been using Primitive values like int, float, char data types
only with the knowledge that these data type can operate and be performed on
without any idea of how they are implemented.

So a user only needs to know what a data type can do, but not how it will be
implemented.
Array as a basic data structure. Representation of data is defined by the
language compiler itself. But the operations on the data are not defined by the
compiler. We have to implement or provide the operations on Array data
structure. So, data structure array and the set of operations together we can call
it as Abstract Data Type (ADT).

Operations on Array Data Structure:

Below is the list of some of the operations that we can perform on an array-
We can perform more operations on the array data structure but the above are some
basic operations. Let us give some information about the above functions-
1. Display () – To Display the entire array on the screen.
2. Add(n) / Append(n) – To add a particular element on the end of the array.
3. Insert (index, n) – To add an element to a particular index.
4. Delete (index) – To delete an element with the help of an index in the given
array.
5. Search (n) – To check whether the given element is present or not in an array.
6. Get (index) – It will return the element which presents on the given index.
7. Set (index, x) – It will change the element with the new element at a particular
index.
8. Max () / Min () – These will return the max and min element in the given array.
9. Reverse () – It will reverse the order of elements in the given array.
10. Shift () – It will shift the whole elements either on the left or right side by
the given number.

2.2 Array applications - Searching

Arrays have a wide range of applications in computer

science and software development. Here are some
common scenarios where arrays are used:

1. Storage and Retrieval: Arrays are ideal for storing

and retrieving data in a sequential manner. They can be
used to store a list of names, addresses, or any other
information that requires straightforward access.
2. Mathematical Computations: Arrays are essential for
performing mathematical computations. They provide a
convenient way to store and manipulate sets of
numbers, making them ideal for tasks like matrix
operations, statistical analysis.

3. Searching and Sorting: Arrays are crucial in

searching and sorting algorithms. Searching algorithms
like linear search and binary search operate on arrays
to locate specific elements efficiently. Sorting
algorithms, such as bubble sort or quick Sort, rearrange
the elements of an array to put them in a specific order.

4. Dynamic Programming: Arrays are heavily used in

dynamic programming, a technique for solving complex
problems by breaking them down into smaller
overlapping sub problems.

Searching

Linear Seraching

The simplest search to be done on an array is the linear

search. This search starts from one end of the array and
keeps iterating until the element is found, or there are no
more elements left (which means that the element does not
exist).
Algorithm for Linear Search Algorithm:
The algorithm for linear search can be broken down into the following
steps:
1. Start: Begin at the first element of the collection of elements.
2. Compare: Compare the current element with the desired element.
3. Found: If the current element is equal to the desired element, return
true or index to the current element.
4. Move: Otherwise, move to the next element in the collection.
5. Repeat: Repeat steps 2-4 until we have reached the end of
collection.
6. Not found: If the end of the collection is reached without finding the
desired element, return that the desired element is not in the array.
7. #include <stdio.h>
8.
9. int search(int arr[], int N, int x)
10. {
11. for (int i = 0; i < N; i++)
12. if (arr[i] == x)
13. return i;
14. return -1;
15. }
16.
17. // Driver code
18. int main(void)
19. {
20. int arr[] = { 2, 3, 4, 10, 40 };
21. int x = 10;
22. int N = sizeof(arr) / sizeof(arr[0]);
23.
24. // Function call
25. int result = search(arr, N, x);
26. (result == -1)
27. ? printf("Element is not present in array")
28. : printf("Element is present at index %d", result);
29. return 0;
30. }