Module 1: Introduction to Data

Structures
 Basic Terminologies: Data
Data refers to raw, unorganized facts that need to be
processed to become meaningful. It can represent
numbers, characters, symbols, or even sounds and images.
Types of Data:
 Quantitative: Numerical (e.g., 100, 45.6)
 Qualitative: Categorical or descriptive (e.g., "Blue", "High")
Characteristics:
 Can be structured (like in databases) or unstructured (like
videos, tweets)
 Meaningless on its own until processed. Alone, they don’t
tell a story.
Example Data: “Kairav”, 25, "CSE", 88.5
 Basic Terminologies: Information
Information is processed data that carries
context, relevance, and meaning. It is useful for
making decisions.
Process: Data → (Processed via algorithms/software) → Information
Difference from Data:
 Data is the input, Information is the output
 Information answers who, what, when, where, and
how.
Example Information: “Kairav, a CSE student aged
25, scored 88.5 in DS"
 Basic Terminologies: Data Structure
A data structure is a logical or mathematical
model used to store, organize, and manage data
efficiently for easy access and modification.
Why are they important?
 Helps handle large data effectively
 Allows faster searching, insertion, deletion, etc.
 Crucial for performance of software systems
Types:
Linear: Data elements are arranged sequentially Examples: Arrays,
Linked Lists, Stacks, Queues
Non-Linear: Data is organized hierarchically or as a network.
Examples: Trees, Graphs
 Basic Terminologies: Elementary Data
Organization
 Primitive Data Types: Basic building blocks provided by
programming languages. Examples: int, float, char,
Boolean
 Derived Data Types: Constructed using primitive types.
Examples: Arrays, Strings, Pointers.
 User-Defined Data Types: Custom structures made using
primitives. Examples: struct, union, class (in C++, Java).
 Abstract Data Types (ADTs): Logical models that define
what data is stored and what operations can be performed-
not how they are implemented. Examples: Stack, Queue,
List, Set, Map
Data Structure Operations
 Insertion: Add new item
 Deletion: Remove item
 Traversal: Access all elements
 Searching: Find an element
 Sorting: Arrange elements in order
 Updation: Modify existing value
 DS Operations: Insertion
 The process of adding a new element into the data structure.
Where you insert:
 At the beginning
 At a specific position
 At the end
Examples:
 Add an element to the end of an array.
 Insert a node into a linked list.
Time Complexity:
 Array (unsorted): O(1) at end, O(n) at specific position
 Linked List: O(1) at beginning, O(n) at specific position
 Real-life Analogy: Adding a new book to a shelf-either at the end,
in the middle, or in a sorted order.
 DS Operations: Deletion
 Removing an existing element from a data
structure.
Scenarios:
 Deleting from the beginning, middle, or end.
 In some structures, you must first search before deleting.
Examples:
 Remove a student’s record from a linked list.
 Delete a value from a stack (only from the top).
Time Complexity:
 Array: O(n) due to shifting elements
 Linked List: O(n) if you must search for the node
 DS Operations: Traversal
 Visiting each element of a data structure once for
processing (e.g., displaying, updating, searching).
Types:
 Linear Traversal (e.g., arrays, linked lists)
 Non-linear Traversal (e.g., tree traversal: in-order, pre-
order, post-order)
Use Cases:
 Printing all student names
 Calculating total marks
Time Complexity:
 Almost always O(n) where n is number of elements
 DS Operations: Searching
 Definition: Finding the location of a given
element in a data structure.
Methods:
 Linear Search: Unsorted list, checks one by one
 Binary Search: Sorted list, divide and conquer
In Complex Structures:
 Trees (e.g., Binary Search Tree): O(log n) on average
 Hash Tables: O(1) average case
Applications:
 Finding a student by roll number
 Searching a file in your folder
 DS Operations: Sorting
Definition: Rearranging elements in a
specific order - increasing or decreasing.
Algorithms:
 Bubble Sort, Insertion Sort, Selection Sort - O(n²)
 Merge Sort, Quick Sort, Heap Sort - O(n log n)
Use Cases:
 Sort exam scores
 Alphabetically arrange names
Importance: Sorted data improves search speed
(especially for Binary Search)
 DS Operations: Updating
Modifying an existing value in the data
structure without adding or deleting
anything.
Use Cases:
 Updating a student’s marks after revaluation
 Editing a contact number in an address book
Time Complexity:
 Depends on the structure and whether the element is
already located
 Direct access (array): O(1)
 After search (linked list): O(n)
 What is an Algorithm?
 An algorithm is a finite, ordered set of well-
defined instructions for solving a specific problem
or performing a task.
 It must be unambiguous, precise, and should lead
to a result after a finite number of steps.
🔁 It’s like a recipe in cooking - exact steps to follow,
in the right order, using defined ingredients.
 Formal Properties of a Good Algorithm

Input: Takes zero or more inputs.

Output: Produces at least one output.
Definiteness: Each step must be clear and
unambiguous.
Finiteness: It must terminate after a finite number of
steps.
Effectiveness: Each operation must be simple
enough to be performed by a machine or human.
 Goals of Algorithm Analysis
Correctness: It should produce the correct
output.
Efficiency: Time and space must be optimized.
Scalability: Should work even as input grows
large.
Maintainability: Easy to understand and
improve.
 How Do We Analyze?
We analyze using:
Time Complexity → How much time does it
take?
Space Complexity → How much memory
does it need?
Use Asymptotic Notations (like O, Θ, Ω) to
express this concisely.
 Example Algorithm: Sum of N Numbers

Step 1: Start
Step 2: Read value of n
Step 3: Initialize sum = 0, i = 1
Step 4: Repeat while i ≤ n
sum = sum + i
i=i+1
Step 5: Print sum
Step 6: Stop
 ✅ Why Analyze Algorithms?
To compare multiple algorithms that solve
the same problem.
Helps determine which algorithm is most
efficient for:
Small vs large datasets
Time-critical vs memory-limited systems
Crucial in designing scalable and optimized
software.
 Best Case
Definition: The minimum amount of time or
steps an algorithm takes when the input is most
favorable.
Example:
Linear Search: If the target is the first element,
it returns immediately.
Notation: Represented using Ω (Omega).
Purpose: Shows how fast the algorithm can be
at its best, but isn’t enough to decide efficiency
alone.
 Average Case
Definition: The expected number of steps
taken over a variety of input scenarios.
Example:
In Linear Search, if the target is in the middle
of the array, average comparisons = n/2.
Importance: Most real-world scenarios fall
under average-case performance.
Notation: Often denoted by Θ (Theta).
 Worst Case
Definition: The maximum time an algorithm
may take on the most difficult input.
Example:
Linear Search: If the target is the last element
or not present, it checks all n elements.
Notation: Denoted by O (Big O).
Use: This is the most commonly used in
industry because it guarantees a performance
ceiling.
 Time Complexity
Definition: Describes how the runtime of an
algorithm grows with respect to the input size
n.
Purpose: Helps estimate execution time
before coding.
Complexity Meaning Example Algorithm
O(1) Constant Time Accessing array element
O(n) Linear Time Linear Search
O(log n) Logarithmic Time Binary Search
O(n²) Quadratic Time Bubble Sort
O(n log n) Log-linear Time Merge Sort
 Space Complexity
 Describes how much additional memory an
algorithm needs as input size increases.
 Includes:
 Input storage
 Temporary variables
 Recursive call stack memory
 Goal: Use minimum memory without compromising
correctness or speed.
 Example:
 A recursive Fibonacci function uses stack space for each call
→ O(n).
 An in-place sorting algorithm like Bubble Sort → O(1)
space.
 Real-World Analogy: Searching in a Library
Scenario: You're in a large university library,
trying to find a specific book among thousands of
bookshelves.
Time Complexity: How many steps or time it takes
to find the book.
 O(1): You already know the exact shelf and position
→ you go directly and pick it.
 O(n): You search shelf by shelf, book by book →
worst if it's the last book.
 O(log n): The library is sorted alphabetically and you
use a search catalog or computer system (like binary
search) to find the location quickly.
 Real-World Analogy: Searching in a Library
Space Complexity: How much memory/space you
need to store extra data or tools while searching.
Carrying a map or using a mobile app to track where
you've already searched = extra memory.
If you memorize everything without tools, you use less
space.
🔹Best Case📘 You walk in and the book is right in front
of you on the first shelf.
🔹Worst Case📕 You search every shelf and every row
and still don’t find the book (it’s not there).
🔹Average Case📗 You search and find the book
somewhere in the middle of your search.
 Asymptotic Notations
✅ What is Asymptotic Analysis?
 It is a mathematical tool used to describe the
efficiency of an algorithm independent of
hardware or input values.
🔍 Instead of exact timing, we focus on how the
algorithm performs as input size (n) → very large
👉 This helps in comparing algorithms under a
standard frame.
 Big O Notation (O) — Worst Case
Definition: Describes the upper bound of time or
space. It gives the maximum time an algorithm will
take for any input size.
Use Case: We always consider the worst-case for
guarantees in systems.
Example:
 Linear Search → O(n)
 Bubble Sort → O(n²)
 Binary Search → O(log n)
Formal Representation: An algorithm is O(f(n)) if ∃
constants c and n₀ such that:
T(n) ≤ c * f(n) for all n ≥ n₀
 Omega Notation (Ω) — Best Case
Definition: Describes the lower bound of time or
space. It gives the minimum time an algorithm
will take for best-case input.
Use Case: Shows how fast an algorithm can run in
the most favorable scenario.
Example:
 Linear Search → Ω(1) if target is at index 0
 Bubble Sort → Ω(n) if the array is already sorted
Formal Representation: An algorithm is Ω(f(n)) if
∃ constants c and n₀ such that:
T(n) ≥ c * f(n) for all n ≥ n₀
 Omega Notation (Ω) — Best Case
Definition: Describes the tight bound — both
upper and lower limits. Means the algorithm’s
running time always grows proportionally to f(n).
Use Case: Used when best = average = worst or
when average case is well understood.
Example:
 Merge Sort → Θ(n log n)
 Binary Search → Θ(log n)
Formal Representation: An algorithm is Θ(f(n)) if
∃ constants c₁, c₂ and n₀ such that:
c₁ * f(n) ≤ T(n) ≤ c₂ * f(n) for all n ≥ n₀
 Common Time Complexities
✅ 1. O(1) – Constant Time
Definition: Time does not change with input size.
Examples:
 Accessing arr[0] in an array
 Pushing/popping from a stack (array-based)
Why it's Fast: The operation happens directly,
without iteration.
🔸 Best possible complexity
 Common Time Complexities
✅ 2. O(log n) – Logarithmic Time
Definition: Time increases logarithmically as input
grows.
Examples:
Binary Search in a sorted array
Searching in a Binary Search Tree (balanced)
Why it's Efficient: With each step, the input is
divided by 2
🔸 Ideal for large datasets where fast lookups are
needed
 Common Time Complexities
✅ 3. O(n) – Linear Time
 Definition: Time grows proportionally to the
input size.
Examples:
Linear Search
Printing all elements in an array
Use Case: When each element must be visited once
🔸 Acceptable for medium-size data, but not scalable
 Common Time Complexities
✅ 4. O(n log n) – Log-linear Time
Definition: More efficient than quadratic, combines
linear and logarithmic growth.
Examples:
Merge Sort, Heap Sort, Quick Sort (avg case)
Why it’s Good:
You divide (log n) and also do work for each element
(n)
🔸 Best possible complexity for comparison-based
sorting
 Common Time Complexities
✅ 5. O(n²) – Quadratic Time
Definition: Time grows quadratically with input
size.
Examples:
Bubble Sort, Selection Sort, Insertion Sort
Why it's Inefficient:
Nested loops over the same dataset
🔺 Avoid for large input — leads to poor
performance
 Common Time Complexities:
Comparison Table
Notation Name Example Behavior as n
Algorithms grows

O(1) Constant Access array element Stays the same

O(log n) Logarithmic Binary Search Grows very slowly

O(n) Linear Linear Search Grows steadily

O(n log n) Log-linear Merge Sort, Heap Sort Grows moderately

O(n²) Quadratic Bubble, Selection Sort Grows very quickly

 Time-Space Tradeoff
 It refers to a balance between the time an
algorithm takes to run and the memory it
consumes.
 Sometimes, you can save time by using more
memory, or save memory by spending more
time.
⚖️ The goal is to find the optimal balance for a
given problem based on available resources.
 Time-Space Tradeoff
🔸Core Idea: You can either compute things on the
fly (time-heavy, memory-light)or store precomputed
results (memory-heavy, time-light).
 ✅ Why It Matters in Real Life
 In mobile devices: Limited RAM, so we may
prefer space-efficient algorithms.
 In high-performance servers: Speed is critical, so
we may sacrifice space.
.
 Time-Space Tradeoff
✅ When to Favor Time Over Space
 You have plenty of RAM or memory available
 Application is real-time, like games, AR/VR,
robotics
 Speed is critical, like in financial trading apps
✅ When to Favor Space Over Time
 Running on embedded systems, IoT devices
 Battery and memory are limited
 Speed is less important than resource
conservation
 Linear Search
Linear Search is a simple searching algorithm
that checks each element one by one in a list until
the target element is found or the end of the list is
reached.
🧠 Key Characteristics
 Works on both sorted and unsorted data
 No need for any pre-processing (like sorting)
 Easy to implement, but not efficient for large
datasets
 Linear Search: 📜 Algorithm Steps
A. Start from the first element.
B. Compare the current element with the target/key.
C. If they match → return the index.
D. If not → move to the next element.
E. Repeat until the target is found or the list ends.
F. If the element is not found, return -1 or "Not
Found".
Linear Search: 📜 C Code Example

int linearSearch(int arr[], int n, int key) {

for(int i = 0; i < n; i++) {
if(arr[i] == key)
return i; // Found at index i
}
return -1; // Not found
}
 Linear Search: Time Complexity

Case Explanation Time

Best Case Element is at the first position O(1)

Element is in the middle or random

Average O(n/2) ≈ O(n)
place

Element is at the last position or not

Worst Case O(n)
found
 Linear Search: 📦 Space Complexity
 O(1) → No extra space used (searching done in-
place)
📌 Advantages
 Simple and easy to implement
 Works for any type of list (sorted or unsorted)
 No overhead of preprocessing or complex logic
⚠️Disadvantages
 Inefficient for large datasets
 Slower compared to more advanced algorithms
like Binary Search
 📚 Where Linear Search is Useful
When the dataset is very small
When the list is unsorted
When the data structure doesn’t support fast
indexing (like Linked List)
In real-world:
Searching a name in a small attendance list
Finding a particular word in a simple unindexed
document
 📊 Linear Search vs. Binary Search

Feature Linear Search Binary Search

Works on Unsorted/Sorted Only Sorted

Time Complexity O(n) O(log n)

Simplicity Very simple Slightly more complex

Space Complexity O(1) O(1)

 Binary Search
Binary Search is a fast and efficient searching
algorithm based on the Divide and Conquer
technique. It works only on sorted arrays by
repeatedly dividing the search interval in half.
📋 Algorithm Idea:
1. Start with the low and high indices of the array.
2. Find the middle index: mid = (low + high)/2
3. If arr[mid] == key → element found.
4. If arr[mid] > key → search the left half.
5. If arr[mid] < key → search the right half.
6. Repeat steps until the key is found or the sub-array
becomes empty.
 Binary Search: 📌 Example
Array (sorted): [10, 20, 30, 40, 50, 60, 70]
Search Key: 50

Step Low High Mid arr[mid] Result

1 0 6 3 40 50 > 40 → right

2 4 6 5 60 50 < 60 → left

3 4 4 4 50 ✅ Found at index 4
Binary Search: 🔣 C Code Example
int binarySearch(int arr[], int n, int key) {
int low = 0, high = n - 1;
while(low <= high) {
int mid = (low + high) / 2;

if(arr[mid] == key)
return mid; // Found
else if(arr[mid] < key)
low = mid + 1;
else
high = mid - 1;
}
return -1; // Not found
}
 Binary Search: Time Complexity

Case Explanation Time

Best Element is at the middle O(1)

Average Cuts array in half until found O(log n)

Worst Element not found or at extreme O(log n)

end
 Binary Search: 💾 Space Complexity
 Iterative Binary Search → O(1)
 Recursive Binary Search → O(log n) due to stack calls
📊 Binary Search Requirements

Requirement Description

✅ Sorted Array Must be in ascending/descending

❌ Unsorted Array Won't work

 Binary Search
🧠 Real-World Use Cases
 Searching names in a sorted phonebook
 Dictionary word lookup
 Auto-suggestions (search narrowing)
 File search in OS directories
 Competitive coding / placement interviews
⚠️Common Mistakes to Avoid:
 Forgetting to sort the array before binary search
 Integer overflow in mid calculation:
 mid = low + (high - low) / 2 is safer than (low + high)/2
 Infinite loops due to incorrect low/high update