A data structure is a way of organizing, storing, and managing data in a computer so it can be used efficiently.

It's a
fundamental concept in computer science, impacting how programs store, retrieve, and manipulate information.
Think of it as a blueprint for organizing data that dictates how data elements relate to each other and how
operations can be performed on them.

● A data structure should be seen as a logical concept that must address two fundamental concerns.

1. First, how the data will be stored, and

2. Second, what operations will be performed on it.

Classification of Data Structures:

▪ Simple Data Structure:

Simple data structure can be constructed with the help of primitive data structure. A primitive data structure used
to represent the standard data types of any one of the computer languages. Variables, arrays, pointers, structures,
unions, etc. are examples of primitive data structures.

▪ Compound Data structure:

Compound data structure can be constructed with the help of any one of the primitive data structure and it is
having a specific functionality. It can be designed by user. It can be classified as
• Linear data structure
• Non-linear data structure

▪ Linear Data Structure:

Linear data structures can be constructed as a continuous arrangement of data elements in the memory. It can be
constructed by using array data type. In the linear Data Structures the relationship of adjacency is maintained
between the data elements.

Operations applied on linear data structure:

The following list of operations applied on linear data structures
1. Add an element
2. Delete an element
3. Traverse
4. Sort the list of elements
5. Search for a data element
For example Stack, Queue, Tables, List, and Linked Lists.
 ▪ Non-linear Data Structure:
Non-linear data structure can be constructed as a collection of randomly distributed set of data item joined
together by using a special pointer (tag). In non-linear Data structure the relationship of adjacency is not maintained
between the data items.

Operations applied on non-linear data structures:

The following list of operations applied on non-linear data structures.
1. Add elements
2. Delete elements
3. Display the elements
4. Sort the list of elements
5. Search for a data element
For example Tree, Decision tree, Graph and Forest

Abstract Data Type (ADT):

An Abstract Data Type (ADT) is a user-defined data type that specifies a set of data values and a set of operations
on those values, while hiding the details of how the data is stored or how the operations are implemented.

Common ADTs include List, Stack, Queue, Circular Queue, Deque (Double-Ended Queue) Tree, Graph, etc.

Example:
Operations in Stack ADT:
Operation Description
push(x) Adds element x to the top of the stack
pop() Removes and returns the top element
Returns the top element without
peek()
removing it
isEmpty() Checks if the stack is empty

Basic Operations in Queue ADT:

Operation Description

enqueue(x) Adds element x to the rear of the queue

dequeue() Removes and returns the front element

peek() Returns the front element without removing it

isEmpty() Checks if the queue is empty

isFull() Checks if the queue is full (for fixed-size

(optional) queues)

❖ Algorithm:
An algorithm is a finite set of well-defined instructions or steps designed to perform a specific task or solve a
particular problem.
Basically, an algorithm takes zero or more set of values, as input and produces a value or set of values, as output.

Algorithm can be specified in any of the three forms given below.

1. In English
2. As a programming language
3. As a pseudo-code

Every algorithm should necessarily satisfy the following criteria:

Input: The algorithm must have input values from a specified set

Output: The algorithm must produce the output values from a specified set of input values. The output values are
the solution to a problem.

Finiteness: For any input the algorithm must terminate after a finite number of steps.

Definiteness: All the steps of the algorithm must be precisely defined.

Effectiveness: It must be possible to perform each step of the algorithm correctly and in a finite amount of TIME.

Different Approaches to Design an Algorithm:

An algorithm does not enforce a language or mode for its expression but only demands adherence to its properties.
Practical Algorithm Design Issues:

1. To save time (Time Complexity): A program that runs faster is a better program.

2. To save space (Space Complexity): A program that saves space over a competing program is considerable
desirable.

Efficiency of Algorithms: The performances of algorithms can be measured on the scales of time and space. The
performance of a program is the amount of computer memory and time needed to run a program. We use two
approaches to determine the performance of a program. One is analytical and the other is experimental. In
performance analysis we use analytical methods, while in performance measurement we conduct experiments.

Time Complexity: The time complexity of an algorithm or a program is a function of the running time of the
algorithm or a program. In other words, it is the amount of computer time it needs to run to completion.

Space Complexity: The space complexity of an algorithm or program is a function of the space needed by the
algorithm or program to run to completion.

The time complexity of an algorithm can be computed either by an empirical or theoretical approach. The empirical
or posteriori testing approach calls for implementing the complete algorithms and executing them on a computer for
various instances of the problem. The time taken by the execution of the programs for various instances of the
problem are noted and compared. The algorithm whose implementation yields the least time is considered as the
best among the candidate algorithmic solutions.

Analyzing Algorithms Suppose M is an algorithm, and suppose n is the size of the input data. Clearly the complexity
f(n) of M increases as n increases. It is usually the rate of increase of f(n) with some standard functions. The most
common computing times are O(1), O(log2 n), O(n), O(n log2 n), O(n2), O(n3), O(2n)
The total frequency counts of the program segments A, B, and C given by 1, (3n+1) and (3n2+3n+1) respectively are
expressed as O(1), O(n), and O(n2). These are referred to as the time complexities of the program segments since
they indicate the running times of the program segments. In a similar manner space complexities of a program can
also be expressed in terms of mathematical notations, which is nothing but the amount of memory they require for
their execution.

1. Initialization: k=1 → 1 opera on

2. Loop Condition Check: k <= n → checked (n+1) mes

3. Body Execution: x=X+2 → executed n mes

4. Increment: k=k+1 → executed n mes

1. Best Case Time Complexity

● Definition: The time taken by the algorithm for the most favorable input (input that causes the algorithm to
perform the fewest operations).

● Notation: Typically denoted as Ω (Omega).

● Example: For linear search, if the element is found at the first index:
● Best Case: Ω(1)

2. Worst Case Time Complexity

● Definition: The time taken for the least favorable input (the input that requires the most operations).

● Notation: Typically denoted as O (Big-O).

● Example: In linear search, if the element is at the last index or not present:
● Worst Case: O(n)

3. Average Case Time Complexity

● Definition: The expected time taken by the algorithm for a typical or random input.

● Notation: Typically denoted as Θ (Theta) or Average-Case.

● Example: For linear search, assuming uniform probability of search target's position:
Average Case: Θ(n)

❖ Asymptotic Notation
Asymptotic notation is a way to describe the efficiency of an algorithm, especially how it behaves as the input size
(n) becomes very large.

It allows us to analyze the time complexity or space complexity of an algorithm independently of hardware,
programming language, or implementation details.
The various asymptotic notations are:

(i) O ( Big Oh notation )

(ii) Ω ( Omega notation )

(iii) θ ( Theta notation )

(iv) o ( Little Oh notation )

(v) ω (Little Omega Notation)

1< log n < n < n log n < n < n^2 < n^3 <.......< 2^n < 3^n <.....<n^n
O ( Big Oh notation )
Big O notation is used to describe the upper bound of an algorithm's running time or space requirement in the
worst-case scenario, as the input size (n) grows very large.

f(n) = O(g(n)) (read as f of n is big oh of g of n) if there exist a positive integer n0 and a positive number c such that
|f(n)| ≤ c|g(n)| for all n ≥ n0 . Here g(n) is the upper bound of the function f(n).

example:
f(n)=2n+3

2n+3 <= c g(n)

Ω ( Omega notation )

Omega notation (Ω) describes the best-case lower bound of an algorithm’s running time or space.

f(n) = Ω(g(n)) ( read as f of n is omega of g of n), if there exists a positive integer n0 and a positive number c such
that |f(n)| ≥ c |g(n)| for all n ≥ n0. Here g(n) is the lower bound of the function f(n).

θ ( Theta notation )

Theta notation (Θ) gives a tight bound on an algorithm’s running time.

For a function g(n), Θ(g(n)) is given by the relation: Θ(g(n)) = { f(n): there exist positive constants c1, c2 and n0 such
that 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ n0 } The above expression can be described as a function f(n) belongs to the
set Θ(g(n)) if there exist positive constants c1 and c2 such that it can be sandwiched between c1g(n) and c2g(n), for
sufficiently large n. If a function f(n) lies anywhere in between c1g(n) and c2g(n) for all n ≥ n0, then f(n) is said to be
asymptotically tight bound.