UNIT -1

Introduction Data, data type, data object.

 Data is any raw fact, figure, or symbol that represents information.
 It can be numbers, text, images, audio, video, or any measurement.
 Example: 45, "Blue", 3.14, True, A+ are all pieces of data.
 In computer science, data is the basic input that computers process to generate
meaningful information.

Data Types
 A data type tells the computer what kind of value is being stored and what operations
can be performed on it.
 Common Data Types:
 Numeric
 Integer (whole numbers) → 1, -25, 2025
 Float/Double (decimal numbers) → 3.14, -0.99
 Character → single letter/symbol (‘A’, ‘b’, ‘$’)
 String → sequence of characters (“Hello”, “OpenAI”)
 Boolean → True / False
 Complex → numbers with real and imaginary parts (e.g., 3 + 2i)
 Example:
If we store age = 22 → Integer type
If we store name = “Ankita” → String type

Data Objects
 A data object is a collection of data values that represent an entity.
 In databases or data mining, a data object is often called a record, tuple, or row.
 Each object has attributes (features/fields/columns) and values.
 Example:
Student Data Object:
 Attributes → Name, Age, Course, Marks
 Values → Ankita, 22, Computer Science, 85
 So here, the whole student entry = data object.
Data structure
A data structure is a specialized format for organizing and storing data. General data structure types
include the array, the file, the record, the table, the tree, and so on. Any data structure is designed to
organize data to suit a specific purpose so that it can be accessed and worked with in appropriate
ways.

Primitive data structures

Primitive data structures are the most basic, fundamental building blocks provided by a
programming language. They are simple and directly operated on by the machine. Examples include
int, float, char, and boolean in languages like C, C++, or Java. These data types store a single value
at a time, and their operations are basic, such as assignment, comparison, and arithmetic operations.
Primitive data structures are the foundation upon which more complex data structures are built. They
are easy to implement and require minimal memory overhead.

non-primitive data structures

non-primitive data structures are more complex and are derived from primitive data types. They
allow the storage and management of collections of values rather than single values. Non-primitive
data structures are classified into linear and non-linear types. Linear data structures include arrays,
linked lists, stacks, and queues, where elements are stored sequentially, and traversal follows a
linear order. Non-linear data structures include trees and graphs, where elements are stored
hierarchically or in interconnected networks, allowing more complex relationships among data. Non-
primitive structures are more versatile and are used to implement sophisticated algorithms, but they
require additional memory and more complex operations compared to primitive types.
Data structures can be classified into two types:

 Linear Data Structures

 Non Linear Data Structures

Linear Data Structures:

Linear data structures are those data structures in which data elements are accessed (read and written)
in sequential fashion ( one by one)

Eg: Stacks , Queues, Lists, Arrays

Non Linear Data Structures:

Non Linear Data Structures are those in which data elements are not accessed in sequential fashion.

Eg: trees, graphs

Difference between Linear and Non-linear Data Structures

[Link] Linear Data Structure Non-linear Data Structure

In a linear data structure, data

elements are arranged in a linear In a non-linear data structure, data
1. order where each and every element elements are attached in
is attached to its previous and next hierarchically manner.
adjacent.

In linear data structure, single level is Whereas in non-linear data structure,

2.
involved. multiple levels are involved.

Its implementation is easy in While its implementation is complex

3. comparison to non-linear data in comparison to linear data
structure. structure.

While in non-linear data structure,

In linear data structure, data elements
4. data elements can't be traversed in a
can be traversed in a single run only.
single run only.

While in a non-linear data structure,

In a linear data structure, memory is memory is utilized in an efficient
5.
not utilized in an efficient way. way.

Its examples are: array, stack, queue, While its examples are: trees and
6.
linked list, etc. graphs.

Applications of linear data structures Applications of non-linear data

7. are mainly in application software structures are in Artificial
development. Intelligence and image processing.

Non-linear data structures are useful

Linear data structures are useful for for representing complex
8. simple data storage and relationships and data hierarchies,
manipulation. such as in social networks, file
systems, or computer networks.

Performance is usually good for

Performance can vary depending on
simple operations like adding or
the structure and the operation, but
9. removing at the ends, but slower for
can be optimized for specific
operations like searching or
operations.
removing elements in the middle.
Operations on data structures
In data structures, the most common operations are traversing, searching, inserting, and deleting.
Each operation has its own definition, procedure, and complexity depending on whether the data
structure is an array, linked list, or another structure.

Traversing
Traversing refers to visiting each element of a data structure exactly once in order to process,
display, or check it. For an array, traversing means moving from the first index to the last index, while
for a linked list, it means starting at the head node and moving through each pointer until the end. For
example, printing all elements of an array is a traversal operation. Since each element must be
accessed, the time complexity of traversal is O(n).

Searching
Searching means finding the location of a specific element in a data structure. The two common
approaches are linear search and binary search. In linear search, each element is checked one by one
until the key is found, which works for both sorted and unsorted data. In binary search, the array must
be sorted, and the middle element is checked repeatedly to reduce the search range by half each time.
For example, searching for the number 45 in an array involves checking each element sequentially in
linear search, while in binary search, the array is divided into halves until the element is found. The
time complexity of linear search is O(n) in the worst case, while binary search reduces it to O(log n).

Inserting
Inserting refers to adding a new element into a data structure at a specific location. In arrays,
insertion at the end is simple and requires O(1) time, but insertion at the beginning or in the middle
requires shifting elements, making the complexity O(n). In linked lists, insertion is more efficient
because it only requires adjusting pointers. Inserting at the beginning of a linked list is O(1), and
inserting at a specific position is O(n), as traversal is required. For example, inserting 25 into the array
[10, 20, 30, 40] at position 2 results in [10, 20, 25, 30, 40].

Deleting
Deleting means removing an element from a data structure. In arrays, if the deletion is at the end, it
takes O(1) time, but if the deletion is from the beginning or middle, elements must be shifted to fill
the gap, which takes O(n) time. In linked lists, deletion is faster since only pointers need to be
changed. Deleting the first node in a linked list takes O(1), but deleting a specific node requires
traversal, so it takes O(n). For example, deleting 20 from the array [10, 20, 30, 40] results in [10, 30,
40].

Complexity analysis
worst case
 In the worst-case analysis, we calculate the upper bound on the running time of an
algorithm. We must know the case that causes a maximum number of operations to be
executed.
 For Linear Search, the worst case happens when the element to be searched (x) is not
present in the array. When x is not present, the search() function compares it with all
the elements of arr[] one by one.
  This is the most commonly used analysis . Most of the time we consider the case that
causes maximum operations.

Best Case Complexity

 Definition: The minimum time (or resources) an algorithm takes to complete, for the
most favorable input.
 Meaning: The fastest the algorithm can possibly run.
 Example (Linear Search): Searching for an element in the first position of an array.
 Time = constant = O(1).

Average Case
 Definition: The expected time (or resources) the algorithm will take for a random
input distribution.
 Meaning: Represents performance for “typical” inputs.
 Example (Linear Search): On average, the searched element might be somewhere in
the middle.
 Time ≈ O(n/2) = O(n).
Time–Space Trade-Off
 An algorithm can often be optimized either for time (execution speed) or for space
(memory usage), but usually not both at the same time.
Examples:
Hash Table: Uses more memory, but searching is very fast (O(1)).
Merge Sort vs. In-Place Quick Sort:
 Merge Sort needs extra memory (O(n)) but is stable and predictable.
 Quick Sort uses less memory (in-place) but may take more time in the worst
case.

Algorithm Efficiency
How well an algorithm uses resources (time & space).
Two key aspects:
Time Efficiency: How fast the algorithm executes (time complexity).
Space Efficiency: How much memory the algorithm needs (space complexity).
Efficient Algorithm: Runs faster and uses less memory compared to alternatives, for large
input sizes.
Asymptotic Notations
 Asymptotic Notations are mathematical tools used to analyze the performance
of algorithms by understanding how their efficiency changes as the input size
grows.
 These notations provide a concise way to express the behavior of an
algorithm's time or space complexity as the input size approaches infinity.
 Asymptotic analysis allows for the comparison of algorithms' space and
time complexities by examining their performance characteristics as the
input size varies.
 By using asymptotic notations, such as Big O, Big Omega, and Big Theta,
we can categorize algorithms based on their worst-case, best-case, or
average-case time or space complexities, providing valuable insights into
their efficiency.
There are mainly three asymptotic notations:
1. Big-O Notation (O-notation)
2. Omega Notation (Ω-notation)
3. Theta Notation (Θ-notation)

Theta Notation (Θ-Notation)

Theta notation encloses the function from above and below. Since it represents
the upper and the lower bound of the running time of an algorithm, it is used for
analyzing the average-case complexity of an algorithm.
Theta (Average Case) You add the running times for each possible input
combination and take the average in the average case.

Big-O Notation (O-notation)

 Big-O notation represents the upper bound of the running time of an
algorithm. Therefore, it gives the worst-case complexity of an algorithm.
 It is the most widely used notation for Asymptotic analysis.
  It specifies the upper bound of a function
 The maximum time required by an algorithm or the worst-case time
complexity.
 It returns the highest possible output value(big-O) for a given input.
 Big-O(Worst Case) It is defined as the condition that allows an algorithm
to complete statement execution in the longest amount of time possible.

Omega Notation (Ω-Notation)

 Omega notation represents the lower bound of the running time of an algorithm.
Thus, it provides the best case complexity of an algorithm.
 The execution time serves as a lower bound on the algorithm's time complexity.
 It is defined as the condition that allows an algorithm to complete statement execution
in the shortest amount of time.