📘 Unit I: Introduction to Data Structures

Complete Exam Notes | BCA /BSCIT/ BIT / MCA / BSc.CSIT

Course Objectives: Explain fundamental concepts and importance of data structures • Define and classify different types of data structures • Differentiate between data structures and ADTs • Analyze and evaluate algorithms in terms of time and space complexity.

1.1 Introduction

Data is the raw material of computation. Every program written in any programming language must deal with data — it must store data, retrieve data, and process data. The way in which we organize data in memory has a tremendous impact on the efficiency of the programs that use it.

Data Structures is the study of how data is organized, stored, and manipulated in a computer so that operations on it can be performed efficiently. It is one of the most fundamental topics in computer science because every algorithm and every program depends on an appropriate organization of data.

Without proper data structures:

Programs become slow and memory-inefficient.
Searching, sorting, and retrieval tasks become unnecessarily complex.
Real-world problems (like GPS navigation, database queries, and social network graphs) become unsolvable in reasonable time.

Why Study Data Structures?

To write efficient programs in terms of time and memory.
To select the right data organization for the right problem.
To form the foundation for advanced topics like algorithms, databases, operating systems, and AI.

1.2 Definition

How computer stores data

Bit (i.e. Binary Digit) is the smallest unit of computer storage.It contains either 0 or 1.

1 𝑏𝑖𝑡 × 8 = 1 𝑏𝑦𝑡𝑒 "01101101 109"
1 𝑏𝑦𝑡𝑒 × 1024 = 1 𝐾𝑖𝑙𝑜𝐵𝑦𝑡𝑒
1 𝐾𝑖𝑙𝑜𝐵𝑦𝑡𝑒 × 1024 = 1 𝑀𝑒𝑔𝑎𝐵𝑦𝑡𝑒

What is Data?

Data refers to a collection of raw facts, figures, or values that by themselves carry no particular meaning. For example: 45, "Ram", 3.14, true.

What is Information?

Information is processed, organized, or structured data that has meaning and context. For example: "Ram scored 45 marks."

What is a Data Structure?

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

A data structure is a logical or mathematical model of a particular organization of data. It defines the relationship between data elements and the operations that can be performed on them.

Key Terms:

Term	Meaning
Data	Raw values or facts
Data Item	A single unit of values
Group Item	Data items that are sub-divided (e.g., Name = First + Last)
Elementary Item	Data items that cannot be further divided
Record	A collection of related data items
File	A collection of related records

Examples of Data Structures:

An array stores a fixed-size sequential collection of elements of the same type.
A linked list stores elements in nodes connected via pointers.
A stack stores elements in LIFO (Last-In-First-Out) order.
A queue stores elements in FIFO (First-In-First-Out) order.
A tree represents hierarchical data.
A graph represents network-like relationships between entities.

1.3 Classification of Data Structures

Data structures are broadly classified into two categories:

DATA STRUCTURES
│
├── Primitive (Basic)
│     ├── int
│     ├── float
│     ├── char
│     └── bool/pointer
│
└── Non-Primitive (Derived)
      │
      ├── Linear
      │     ├── Static
      │     │     └── Array
      │     └── Dynamic
      │           ├── Linked List
      │           ├── Stack
      │           └── Queue
      │
      └── Non-Linear
            ├── Trees
            │     ├── Binary Tree
            │     ├── Binary Search Tree
            │     ├── AVL Tree
            │     └── Heap
            └── Graphs
                  ├── Directed
                  └── Undirected

1.3.1 Primitive Data Structures

Primitive data structures are the basic data types directly supported by the machine and programming language. They hold a single value and have a predefined size.

Type	Size	Range
int	2 or 4 bytes	-32768 to 32767 / -2³¹ to 2³¹-1
float	4 bytes	±3.4 × 10³⁸
char	1 byte	0 to 255
bool	1 byte	true / false
pointer	4 or 8 bytes	Memory address

1.3.2 Non-Primitive Data Structures

These are complex structures derived from primitive ones.

A) Linear Data Structures

In linear data structures, elements are arranged in a sequential manner — each element has one predecessor and one successor (except the first and last).

i) Array

Fixed-size collection of elements of the same type stored in contiguous memory.
Supports random access using index.
Operations: Traversal, Insertion, Deletion, Searching.

int arr[5] = {10, 20, 30, 40, 50};
// arr[0] = 10, arr[1] = 20, ...
// Memory: | 10 | 20 | 30 | 40 | 50 |
//         [100][104][108][112][116]  (assuming int = 4 bytes)

ii) Linked List

A dynamic data structure where each element (node) contains data and a pointer to the next node.
Types: Singly Linked List, Doubly Linked List, Circular Linked List.

[10|→] → [20|→] → [30|→] → [40|NULL]
 HEAD

iii) Stack

Follows LIFO (Last In, First Out) principle.
Operations: Push (insert), Pop (delete), Peek (top element).
Real-world use: Undo in text editors, function call stack, expression evaluation.

TOP →  | 30 |  ← Last pushed
       | 20 |
       | 10 |  ← First pushed
BOTTOM

iv) Queue

Follows FIFO (First In, First Out) principle.
Operations: Enqueue (insert), Dequeue (delete), Front, Rear.
Real-world use: CPU scheduling, printer spooling, BFS traversal.

FRONT → [10] [20] [30] [40] ← REAR
         (Dequeue from front, Enqueue at rear)

B) Non-Linear Data Structures

In non-linear data structures, elements are not arranged in a sequential manner. An element can be connected to more than one other element.

i) Trees

Hierarchical structure with a root node and subtrees of children.
No cycles allowed.

        [A]           ← Root (Level 0)
       /   \
     [B]   [C]        ← Level 1
    /   \    \
  [D]  [E]  [F]       ← Level 2 (Leaf nodes: D, E, F)

ii) Graphs

A set of vertices (nodes) connected by edges.
Can be directed or undirected, weighted or unweighted.
Real-world use: Social networks, Google Maps, Internet routing.

Undirected Graph:      Directed Graph:
  A --- B               A --> B
  |     |               |     |
  C --- D               v     v
                        C --> D

1.3.3 Static vs Dynamic Data Structures

Feature	Static	Dynamic
Memory allocated	At compile time	At runtime
Size	Fixed	Variable
Example	Array	Linked List, Stack, Queue
Memory use	May waste memory	Efficient
Speed	Fast access	Slightly slower

1.4 Abstract Data Type (ADT)

Data type

In a broad sense, there are three types of data types:

** Fundamental (Basics) data types ** Predefined data types which are used by the programmer directly to store only one value as per requirement; i.e. integer type, character type, etc.

** Derived data types ** Derived using built in data type which are designed by the programmer to store multiple values of same type as per their requirement. For example: array, functions, pointers, etc.

** User-defined data types ** Derived using built-in data types which are wrapped into a single data type to store multiple values of either same type or different type or both as per their requirement. For example: class, structure, etc.

Definition

An Abstract Data Type (ADT) is a mathematical model of a data structure that specifies the type of data stored, the operations supported, and the types of parameters of the operations — WITHOUT specifying the implementation details.

The word "Abstract" means we focus on WHAT the data structure does, not HOW it does it. The implementation is hidden from the user.

properties

Abstract Data Types (ADT) are entities that are definitions of data and operations but do not have implementation details.
ADT is a data type whose representation is hidden from, and of no concern to the application code.
ADT is a useful tool for specifying the logical properties of a data type.
For example, when writing application code, we don’t care how strings are represented; we just declare variables of type string, and manipulate them by using string operations.

An ADT consists of:

Data — what is stored
Operations — what can be done with the data
Error conditions — what errors might arise

ADT Example: Stack

ADT Stack {
    Data:
        - A collection of elements with LIFO ordering

    Operations:
        - push(element)  : Add element to top
        - pop()          : Remove and return top element
        - peek()         : Return top element without removing
        - isEmpty()      : Return true if stack is empty
        - size()         : Return number of elements

    Error Conditions:
        - pop() on empty stack → Underflow error
        - push() on full stack → Overflow error (if bounded)
}

The user knows: "I can push and pop elements." They don't care if it's implemented with an array or a linked list — that's the essence of abstraction.

ADT Example: Queue

ADT Queue {
    Data:
        - A collection of elements with FIFO ordering

    Operations:
        - enqueue(element) : Add element to rear
        - dequeue()        : Remove and return front element
        - front()          : Return front element
        - isEmpty()        : Return true if queue is empty
        - size()           : Return number of elements
}

Why ADTs are Important

Encapsulation — Hides internal complexity from users.
Modularity — Different implementations can be swapped without changing the user code.
Reusability — ADTs are reusable across different programs and languages.
Maintainability — Changes in implementation don't affect the user interface.

1.5 Comparison Between Data Structure and ADT

This is one of the most important distinctions in the course.

Aspect	Data Structure	Abstract Data Type (ADT)
Definition	Concrete implementation of data organization in memory	Mathematical/logical model of data and operations
Focus	HOW data is stored and accessed	WHAT operations are supported
Level	Implementation level	Specification / Design level
Details	Exposes memory layout, pointers, indices	Hides implementation details
Language dependency	Yes (code-specific)	No (language-independent)
Example	Array, Linked List	Stack ADT, Queue ADT, List ADT
User concern	Memory allocation, pointer manipulation	Only the operations available

Analogy: Think of an ADT as a TV remote control specification: it says "has power button, volume up/down, channel change." The data structure is the actual remote built by a manufacturer — one might use infrared, another Bluetooth, but both satisfy the specification.

1.6 Algorithm

Definition

An algorithm is a finite set of well-defined, unambiguous instructions that, when executed in the given sequence, solves a problem or completes a task in a finite amount of time.

The word "algorithm" is derived from the name of Persian mathematician Muhammad ibn Musa al-Khwarizmi (9th century).

Properties of a Good Algorithm

An algorithm must satisfy these five properties:

Property	Description
Input	Has zero or more inputs from an external source
Output	Produces at least one output
Definiteness	Every step is clearly and unambiguously defined
Finiteness	Must terminate after a finite number of steps
Effectiveness	Each step is basic enough to be carried out by a person with pencil and paper

Representation of Algorithms

Algorithms can be expressed as:

Natural Language — English description (ambiguous)
Pseudocode — Structured English-like notation (most common)
Flowchart — Graphical representation using symbols

Flowchart Symbols:

[Oval]      → Start / End (Terminal)
[Rectangle] → Process / Computation
[Diamond]   → Decision (Yes/No)
[Parallelogram] → Input / Output
[Arrow]     → Flow of control

Example — Algorithm to find the largest of three numbers:

Algorithm: FindMax(A, B, C)
Input: Three numbers A, B, C
Output: The largest number

Step 1: Start
Step 2: Read A, B, C
Step 3: Set Max = A
Step 4: If B > Max then Max = B
Step 5: If C > Max then Max = C
Step 6: Print Max
Step 7: Stop

Pseudocode:

MAX(A, B, C):
    max ← A
    if B > max:
        max ← B
    if C > max:
        max ← C
    return max

C Program:

#include <stdio.h>

int findMax(int a, int b, int c) {
    int max = a;
    if (b > max) max = b;
    if (c > max) max = c;
    return max;
}

int main() {
    int a, b, c;
    printf("Enter three numbers: ");
    scanf("%d %d %d", &a, &b, &c);
    printf("Maximum = %d\n", findMax(a, b, c));
    return 0;
}

Java Program:

import java.util.Scanner;

public class Main {

    public static int findMax(int a, int b, int c) {
        int max = a;
        if (b > max) max = b;
        if (c > max) max = c;
        return max;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("Enter three numbers: ");
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        int c = scanner.nextInt();

        System.out.println("Maximum = " + findMax(a, b, c));

        scanner.close();
    }
}

1.7 Analysis of Algorithms

Why Analyze Algorithms?

Given two algorithms that solve the same problem, we need a way to compare them to determine which is better. We cannot simply measure runtime on a computer because:

Different computers have different speeds.
Runtime depends on input size and type.
We want a general, machine-independent measure.

Algorithm analysis provides a theoretical framework to evaluate the efficiency of algorithms in terms of:

Time Complexity — How much time (number of steps) the algorithm takes.
Space Complexity — How much memory (storage) the algorithm uses.

Asymptotic Notations

Asymptotic notation describes how the performance of an algorithm scales as the input size n grows toward infinity. These are mathematical tools to describe the growth rate.

1. Big-O Notation — O(f(n)) [Upper Bound / Worst Case]

Big-O gives the WORST CASE running time of an algorithm. It is the most commonly used notation.

Definition: T(n) = O(f(n)) if there exist positive constants c and n₀ such that:

T(n) ≤ c × f(n)    for all n ≥ n₀

Common Big-O Classes (ordered from best to worst):

Notation	Name	Example
O(1)	Constant	Accessing array element
O(log n)	Logarithmic	Binary search
O(n)	Linear	Linear search
O(n log n)	Linearithmic	Merge sort
O(n²)	Quadratic	Bubble sort
O(n³)	Cubic	Matrix multiplication
O(2ⁿ)	Exponential	Recursive Fibonacci
O(n!)	Factorial	Traveling salesman (brute force)

Growth Rate Visualization:

Running
 Time
  |                                    O(n!)
  |                               O(2ⁿ)
  |                          O(n³)
  |                     O(n²)
  |                O(n log n)
  |           O(n)
  |      O(log n)
  | O(1)
  +---------------------------------> n (Input Size)

2. Omega Notation — Ω(f(n)) [Lower Bound / Best Case]

Omega gives the BEST CASE running time of an algorithm.

Definition: T(n) = Ω(f(n)) if there exist positive constants c and n₀ such that:

T(n) ≥ c × f(n)    for all n ≥ n₀

Example: Linear search has Ω(1) — best case is when the element is found at the first position.

3. Theta Notation — Θ(f(n)) [Tight Bound / Average Case]

Theta gives the AVERAGE CASE and represents both upper and lower bounds.

Definition: T(n) = Θ(f(n)) if there exist positive constants c₁, c₂ and n₀ such that:

c₁ × f(n) ≤ T(n) ≤ c₂ × f(n)    for all n ≥ n₀

Rules for Calculating Time Complexity

Rule 1: Constant time operations → O(1)

public class Main {
    public static void main(String[] args) {
        int x = 5;   // O(1)
        x = x + 1;   // O(1)

        System.out.println(x);
    }
}

Rule 2: Loop → O(n)

public class Main {
    public static void main(String[] args) {
        int n = 5;

        for (int i = 0; i < n; i++) {   // runs n times
            System.out.print(i);        // O(1) each time
        }
    }
}
// Total: O(n)

Rule 3: Nested loops → O(n²)

public class Main {
    public static void main(String[] args) {
        int n = 5;

        for (int i = 0; i < n; i++) {         // runs n times
            for (int j = 0; j < n; j++) {     // runs n times for each i
                System.out.println(i + " " + j);  // O(1)
            }
        }
    }
}
// Total: O(n × n) = O(n²)

Rule 4: Consecutive statements → add

public class Main {
    public static void main(String[] args) {
        int n = 5;

        // First loop → O(n)
        for (int i = 0; i < n; i++) {
            System.out.println("i = " + i);
        }

        // Second loop → O(n)
        for (int j = 0; j < n; j++) {
            System.out.println("j = " + j);
        }
    }
}
// Total: O(n) + O(n) = O(2n) 
// Drop constant → O(n)
// = overall time complexity = O(n)

Rule 5: Halving per step → O(log n)

public class Main {
    public static void main(String[] args) {
        int n = 16;
        int i = 1;

        while (i < n) {
            System.out.println(i);
            i = i * 2;   // doubles each time
        }
    }
}
// Runs log₂(n) times → Time Complexity = O(log n)
// i starts from 1
// Each iteration: i = i * 2 → values become:
//        1 → 2 → 4 → 8 → 16 ...
// Number of steps ≈ log₂(n)

1.8 Design of Algorithms

There are several standard strategies (paradigms) for designing algorithms. Two of the most fundamental are:

1.8.1 Incremental Approach

In the incremental approach, the solution to a problem is built by adding one element at a time to a partially built solution, extending it until the complete solution is obtained.

Core Idea:

Start with a trivially small instance.
Extend the solution step-by-step, one element at a time.
At each step, the partial solution is valid/correct.

Classic Example: Insertion Sort

In insertion sort, we sort the array by picking one element at a time and inserting it into its correct position in the already-sorted portion.

Initial:   [5, 2, 4, 6, 1, 3]
           [5] is sorted (trivially)
Step 1:    Insert 2 → [2, 5] | 4, 6, 1, 3
Step 2:    Insert 4 → [2, 4, 5] | 6, 1, 3
Step 3:    Insert 6 → [2, 4, 5, 6] | 1, 3
Step 4:    Insert 1 → [1, 2, 4, 5, 6] | 3
Step 5:    Insert 3 → [1, 2, 3, 4, 5, 6]

C Program — Insertion Sort:

public class Main {

    public static void insertionSort(int[] arr, int n) {
        int i, key, j;

        for (i = 1; i < n; i++) {
            key = arr[i];      // Element to be inserted
            j = i - 1;

            // Shift elements greater than key one position right
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }

            arr[j + 1] = key;  // Place key in correct position
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 4, 6, 1, 3};
        int n = arr.length;

        insertionSort(arr, n);

        System.out.print("Sorted: ");
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}
// Output: Sorted: 1 2 3 4 5 6

Complexity of Insertion Sort:

Case	Time	Condition
Best	O(n)	Already sorted
Average	O(n²)	Random order
Worst	O(n²)	Reverse sorted

1.8.2 Divide and Conquer

In the divide and conquer approach, the problem is divided into smaller subproblems of the same type, each subproblem is solved independently (often recursively), and the solutions are combined to get the final answer.

Three Steps:

1. DIVIDE   → Break the problem into smaller subproblems
2. CONQUER  → Solve each subproblem recursively
3. COMBINE  → Merge the solutions of subproblems

Classic Example: Merge Sort

Merge sort divides the array into two halves, sorts each half recursively, and then merges the two sorted halves.

Divide:
        [38, 27, 43, 3, 9, 82, 10]
              /              \
      [38, 27, 43]       [3, 9, 82, 10]
        /       \           /       \
    [38, 27]  [43]      [3, 9]   [82, 10]
     /    \               /  \     /    \
   [38]  [27]           [3]  [9] [82] [10]

Conquer (Sort):
   [38]  [27]  →  [27, 38]
   [3]  [9]    →  [3, 9]
   [82] [10]   →  [10, 82]

Combine (Merge):
   [27, 38] + [43]       → [27, 38, 43]
   [3, 9] + [10, 82]     → [3, 9, 10, 82]
   [27, 38, 43] + [3, 9, 10, 82] → [3, 9, 10, 27, 38, 43, 82]

Java Program — Merge Sort:

public class Main {

    public static void merge(int[] arr, int l, int m, int r) {
        int n1 = m - l + 1;
        int n2 = r - m;

        int[] L = new int[n1];
        int[] R = new int[n2];

        // Copy data to temp arrays
        for (int i = 0; i < n1; i++)
            L[i] = arr[l + i];
        for (int j = 0; j < n2; j++)
            R[j] = arr[m + 1 + j];

        int i = 0, j = 0, k = l;

        // Merge the temp arrays
        while (i < n1 && j < n2) {
            if (L[i] <= R[j])
                arr[k++] = L[i++];
            else
                arr[k++] = R[j++];
        }

        // Copy remaining elements
        while (i < n1)
            arr[k++] = L[i++];
        while (j < n2)
            arr[k++] = R[j++];
    }

    public static void mergeSort(int[] arr, int l, int r) {
        if (l < r) {
            int m = l + (r - l) / 2;

            mergeSort(arr, l, m);       // Divide left
            mergeSort(arr, m + 1, r);   // Divide right
            merge(arr, l, m, r);        // Combine
        }
    }

    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        int n = arr.length;

        mergeSort(arr, 0, n - 1);

        System.out.print("Sorted: ");
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
    }
}
// Output: Sorted: 3 9 10 27 38 43 82

Complexity of Merge Sort:

Case	Time
Best	O(n log n)
Average	O(n log n)
Worst	O(n log n)

Comparison: Incremental vs Divide and Conquer

Feature	Incremental	Divide and Conquer
Strategy	Extend partial solution step by step	Break into subproblems, solve, combine
Recursion	Not always used	Typically recursive
Example	Insertion Sort	Merge Sort, Quick Sort, Binary Search
Space	O(1) typically	O(n) or O(log n) stack space
Best for	Small or nearly sorted data	Large datasets
Parallelism	Hard to parallelize	Easy to parallelize

1.9 Performance Analysis and Measurement

Performance analysis is the theoretical evaluation of an algorithm's efficiency using mathematical models. Performance measurement is the actual empirical timing of an algorithm on a specific machine.

1.9.1 Space Complexity

Space complexity is the total amount of memory space required by an algorithm as a function of the input size.

Components of Space:

Total Space = Fixed Space + Variable Space

Fixed Space (S_c):
  - Instruction space (program code)
  - Space for constants and fixed variables
  - Independent of input size

Variable Space (S_p(I)):
  - Space for data structures that grow with input
  - Recursion stack space
  - Depends on input instance I

Space Complexity = S(P) = S_c + S_p(I)

Example 1 — Simple Sum:

public class Main {

    public static int sum(int a, int b) {
        return a + b;
    }

    public static void main(String[] args) {
        int result = sum(5, 3);
        System.out.println("Sum = " + result);
    }
}

Space: O(1) — only two integers, no extra space needed.

Example 2 — Sum of Array:

public class Main {

    public static int arraySum(int[] arr, int n) {
        int sum = 0;   // 1 variable

        for (int i = 0; i < n; i++) {
            sum += arr[i];
        }

        return sum;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        int n = arr.length;

        int result = arraySum(arr, n);
        System.out.println("Sum = " + result);
    }
}

Space: O(1) auxiliary (the array itself is input, not counted as extra)

Example 3 — Recursive Factorial (Recursion Stack Space):

public class Main {

    public static int factorial(int n) {
        if (n == 0) return 1;
        return n * factorial(n - 1);  // recursive call
    }

    public static void main(String[] args) {
        int n = 5;

        int result = factorial(n);
        System.out.println("Factorial of " + n + " = " + result);
    }
}

factorial(5)
  → factorial(4)
      → factorial(3)
          → factorial(2)
              → factorial(1)
                  → factorial(0) ← base case

Stack Depth = n → Space Complexity = O(n)

Space Complexity Summary Table:

Algorithm	Auxiliary Space
Iterative loop	O(1)
Binary Search (iterative)	O(1)
Recursive Factorial	O(n)
Merge Sort	O(n)
Quick Sort	O(log n) average
BFS (Graph)	O(V + E)

1.9.2 Time Complexity

Time complexity is the amount of time (number of basic operations) required by an algorithm as a function of the input size n.

It is expressed using Big-O notation to represent the worst-case scenario.

Step-by-Step Calculation Examples:

Example 1 — Single Loop:

public class Main {
    public static void main(String[] args) {
        int n = 5;

        for (int i = 0; i < n; i++) {   // n iterations
            System.out.print(i + " ");  // 1 operation (O(1))
        }
    }
}
// Time Complexity: O(n)
// Output : 0 1 2 3 4

Example 2 — Nested Loop:

public class Main {
    public static void main(String[] args) {
        int n = 3;

        for (int i = 0; i < n; i++) {          // n iterations
            for (int j = 0; j < n; j++) {      // n iterations for each i
                System.out.println(i + " " + j);  // O(1)
            }
        }
    }
}
// Total operations = n × n = n²
// Time Complexity: O(n²)
// Output: 
// 0 0
// 0 1
// 0 2
// ... and so on until 2 2

Example 3 — Binary Search (Logarithmic):

public class Main {

    public static 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;
            }
            else if (arr[mid] < key) {
                low = mid + 1;
            }
            else {
                high = mid - 1;
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11};
        int n = arr.length;
        int key = 7;

        int result = binarySearch(arr, n, key);

        if (result != -1) {
            System.out.println("Found at index: " + result);
        } else {
            System.out.println("Not found");
        }
    }
}
// Found at index: 3
// Each iteration halves the search space
// Time Complexity: O(log n)

Binary Search trace on {1, 3, 5, 7, 9, 11} searching for 7:

Step 1: low=0, high=5, mid=2 → arr[2]=5 < 7 → low=3
Step 2: low=3, high=5, mid=4 → arr[4]=9 > 7 → high=3
Step 3: low=3, high=3, mid=3 → arr[3]=7 == 7 → Found!

Only 3 steps for 6 elements → log₂(6) ≈ 2.58 → O(log n)

Example 4 — Bubble Sort:

public class Main {

    public static void bubbleSort(int[] arr, int n) {
        for (int i = 0; i < n - 1; i++) {              // n-1 passes
            for (int j = 0; j < n - i - 1; j++) {      // n-i-1 comparisons
                if (arr[j] > arr[j + 1]) {

                    // swap
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 1, 4, 2, 8};
        int n = arr.length;

        bubbleSort(arr, n);

        System.out.print("Sorted: ");
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}
// Sorted: 1 2 4 5 8
// Total comparisons: (n-1) + (n-2) + ... + 1 = n(n-1)/2
// Time Complexity: O(n²)
// Worst case: O(n²)
// Best case (optimized version): O(n²) (unless early exit is added)

Example 5 — Recursive Fibonacci:

public class Main {

    public static int fib(int n) {
        if (n <= 1) {
            return n;
        }
        return fib(n - 1) + fib(n - 2);
    }

    public static void main(String[] args) {
        int n = 5;

        int result = fib(n);
        System.out.println("Fibonacci of " + n + " = " + result);
    }
}
// Fibonacci of 5 = 5
// Each call branches into 2 calls
// Call tree has ~2ⁿ nodes
// Time Complexity: O(2ⁿ)  ← Exponential!

         fib(4)
        /       \
    fib(3)     fib(2)
    /    \     /    \
 fib(2) fib(1) fib(1) fib(0)
 /    \
fib(1) fib(0)

Comparison Table of Sorting Algorithms

Algorithm	Best Case	Average Case	Worst Case	Space
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)
Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)

Performance Measurement (Empirical Analysis)

While theoretical analysis uses mathematical models, performance measurement involves:

Implementing the algorithm in a programming language.
Running it with various input sizes.
Measuring actual wall-clock time.

public class Main {

    // Bubble Sort (for testing performance)
    public static void bubbleSort(int[] arr, int n) {
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {

        int n = 10000;
        int[] arr = new int[n];

        // Reverse sorted (worst case)
        for (int i = 0; i < n; i++) {
            arr[i] = n - i;
        }

        // Start time (nanoseconds)
        long start = System.nanoTime();

        bubbleSort(arr, n);

        // End time
        long end = System.nanoTime();

        double timeTaken = (end - start) / 1e9; // convert to seconds

        System.out.println("Time taken: " + timeTaken + " seconds");
    }
}

Limitations of Empirical Analysis:

Results depend on hardware, OS, and compiler.
Cannot predict performance for all input sizes.
Theoretical analysis is preferred for generalization.

Summary Table: Unit I at a Glance

Topic	Key Point
Data Structure	Method to organize and store data efficiently
Primitive DS	Basic types: int, float, char, pointer
Non-Primitive DS	Derived: Arrays, Lists, Stacks, Queues, Trees, Graphs
Linear DS	Sequential organization (Array, Stack, Queue, Linked List)
Non-Linear DS	Hierarchical/Network organization (Trees, Graphs)
ADT	Logical model — defines WHAT, not HOW
DS vs ADT	DS = implementation; ADT = specification
Algorithm	Finite set of unambiguous steps to solve a problem
Algorithm Properties	Input, Output, Definiteness, Finiteness, Effectiveness
Incremental	Build solution one element at a time (e.g., Insertion Sort)
Divide & Conquer	Divide → Conquer → Combine (e.g., Merge Sort)
Big-O	Worst-case upper bound
Omega	Best-case lower bound
Theta	Average-case tight bound
Space Complexity	Memory used by algorithm
Time Complexity	Number of operations as a function of n

Important Questions for Exam

Define data structure. Explain the classification of data structures with a neat diagram.
What is an Abstract Data Type (ADT)? Explain with an example.
Differentiate between data structure and ADT.
What is an algorithm? What are the properties of a good algorithm?
Explain the incremental approach to algorithm design with an example.
Explain the divide and conquer approach with the Merge Sort example.
Define time complexity and space complexity. Calculate the time complexity of bubble sort.
Explain Big-O, Omega, and Theta notation with examples.
What is the difference between static and dynamic data structures?
Write an algorithm for binary search and analyze its time complexity.

LAB:

Explain the classification of Data Structures and ADT, then write algorithms/pseudocode for largest number, reverse number, Stack and Queue operations, and analyze their time and space complexity using Incremental and Divide and Conquer approaches.

End of Unit I — Introduction to Data Structures Prepared for: BCA / BSCIT / BIT / MCA / BSc.CSIT | Subject: Data Structures and Algorithms

Part-1 Data Structure & Algorithm

📘 Unit I: Introduction to Data Structures

Complete Exam Notes | BCA /BSCIT/ BIT / MCA / BSc.CSIT

1.1 Introduction

1.2 Definition

How computer stores data

What is Data?

What is Information?

What is a Data Structure?

1.3 Classification of Data Structures

1.3.1 Primitive Data Structures

1.3.2 Non-Primitive Data Structures

A) Linear Data Structures

B) Non-Linear Data Structures

1.3.3 Static vs Dynamic Data Structures

1.4 Abstract Data Type (ADT)

Data type

Definition

properties

ADT Example: Stack

ADT Example: Queue

Why ADTs are Important

1.5 Comparison Between Data Structure and ADT

1.6 Algorithm

Definition

Properties of a Good Algorithm

Representation of Algorithms

1.7 Analysis of Algorithms

Why Analyze Algorithms?

Asymptotic Notations

1. Big-O Notation — O(f(n)) [Upper Bound / Worst Case]

2. Omega Notation — Ω(f(n)) [Lower Bound / Best Case]

3. Theta Notation — Θ(f(n)) [Tight Bound / Average Case]

Rules for Calculating Time Complexity

1.8 Design of Algorithms

1.8.1 Incremental Approach

1.8.2 Divide and Conquer

Comparison: Incremental vs Divide and Conquer

1.9 Performance Analysis and Measurement

1.9.1 Space Complexity

1.9.2 Time Complexity

Comparison Table of Sorting Algorithms

Performance Measurement (Empirical Analysis)

Summary Table: Unit I at a Glance

Important Questions for Exam

LAB: