Unit 1: Introduction, Arrays, Sorting and Searching

1. Executive Summary & Foundational Concepts

A Data Structure is a systematic mathematical and logical arrangement for organizing, managing, and storing data within a digital computer to enable efficient access and modification. The choice of appropriate data structures directly dictates the algorithmic efficiency, memory footprint, and architectural scalability of computational software.

Primary Classifications of Data Structures:

1. Primitive vs. Non-Primitive:
   • Primitive Data Structures: Basic atomic types natively supported by hardware architecture and machine instructions (e.g., int, float, char, pointer).
   • Non-Primitive Data Structures: Complex composite structures constructed from primitive types to model relationships (e.g., arrays, linked lists, trees, graphs).
2. Linear vs. Non-Linear:
   • Linear Data Structures: Elements form a sequential sequence where each element (except first and last) has a unique predecessor and successor (e.g., Arrays, Stacks, Queues, Linked Lists). Traversal is single-level and sequential.
   • Non-Linear Data Structures: Elements are organized hierarchically or interconnected arbitrarily across multi-level relationships (e.g., Trees, Graphs). Traversal requires branching paths.
3. Static vs. Dynamic:
   • Static Data Structures: Fixed size allocated at compile time; memory bounds cannot expand or contract during program execution (e.g., standard fixed-size arrays).
   • Dynamic Data Structures: Flexible size allocated from heap storage during runtime; capacity expands and shrinks as elements are added or removed (e.g., linked lists, dynamic arrays/vectors).

2. Asymptotic Notations & Algorithmic Complexity

Algorithmic efficiency is measured in two dimensions:

• Time Complexity: The mathematical relationship quantifying the number of fundamental operations executed as a function of input size $N$.
• Space Complexity: The total memory storage (fixed instruction space + dynamic variable space) required as a function of input size $N$.
• Time-Space Trade-off: The design compromise where execution speed is accelerated by consuming additional memory storage (e.g., lookup tables, hash maps), or memory usage is conserved at the expense of higher CPU computation cycles.

Formal Asymptotic Notations:

Growth Order: O(1) < O(log N) < O(N) < O(N log N) < O(N^2) < O(2^N) < O(N!)

1. Big-O Notation ($O$) - Asymptotic Upper Bound:
   Represents the worst-case ceiling. Formally, $f(N) = O(g(N))$ if there exist positive constants $c$ and $N_0$ such that:
   $0 \le f(N) \le c \cdot g(N) \quad \forall N \ge N_0$
2. Omega Notation ($\Omega$) - Asymptotic Lower Bound:
   Represents the best-case floor. Formally, $f(N) = \Omega(g(N))$ if there exist positive constants $c$ and $N_0$ such that:
   $0 \le c \cdot g(N) \le f(N) \quad \forall N \ge N_0$
3. Theta Notation ($\Theta$) - Asymptotically Tight Bound:
   Binds the function from both above and below. Formally, $f(N) = \Theta(g(N))$ if and only if $f(N) = O(g(N))$ and $f(N) = \Omega(g(N))$:
   $c_1 \cdot g(N) \le f(N) \le c_2 \cdot g(N) \quad \forall N \ge N_0$
4. Little-o ($o$) and Little-omega ($\omega$):
   • $f(N) = o(g(N))$ denotes a strict upper bound: $\lim_{N \to \infty} \frac{f(N)}{g(N)} = 0$.
   • $f(N) = \omega(g(N))$ denotes a strict lower bound: $\lim_{N \to \infty} \frac{f(N)}{g(N)} = \infty$.

3. Linear Arrays: Memory Organization & Address Calculations

A Linear Array is a homogeneous, contiguous collection of elements identified by consecutive integer index bounds $[LB, UB]$ where $LB$ is the Lower Bound and $UB$ is the Upper Bound. The total number of elements (Length) is:
$\text{Length} = UB - LB + 1$

A. One-Dimensional (1D) Array Address Mapping

Because elements occupy contiguous physical RAM addresses, the memory location of element $A[i]$ is calculated in $O(1)$ time using the Base Address ($BA$) and element width ($W$ in bytes):
$\text{Address}(A[i]) = BA + W \times (i - LB)$

Example: For an array $A[10 \dots 50]$ with $BA = 2000$ and element size $W = 4$ bytes, the address of $A[25]$ is:
$\text{Address}(A[25]) = 2000 + 4 \times (25 - 10) = 2000 + 4 \times 15 = 2060$

B. Two-Dimensional (2D) Array Address Mapping

A 2D array of dimensions $M \times N$ (rows $0 \dots M-1$, columns $0 \dots N-1$) can be linearized in RAM using two canonical conventions:

1. Row-Major Order (RMO):
   Elements are stored row after row in contiguous physical memory.
   $\text{Address}(A[i][j]) = BA + W \times [(i - LB_r) \times C + (j - LB_c)]$
   where $C$ is the total number of columns ($UB_c - LB_c + 1$).

2. Column-Major Order (CMO):
   Elements are stored column after column in contiguous physical memory.
   $\text{Address}(A[i][j]) = BA + W \times [(j - LB_c) \times R + (i - LB_r)]$
   where $R$ is the total number of rows ($UB_r - LB_r + 1$).

4. Fundamental Array Operations

1. Traversal: Visiting each element exactly once to inspect, display, or transform values. Time complexity: $O(N)$.
2. Insertion:
   • At the end (with available capacity): $O(1)$ operations.
   • At index $K$ / beginning: Requires shifting elements from index $K$ up to $N-1$ one position to the right. Worst-case time complexity: $O(N)$.
3. Deletion:
   • At the end: $O(1)$ operations.
   • At index $K$ / beginning: Requires shifting elements from index $K+1$ down to $N-1$ one position to the left. Worst-case time complexity: $O(N)$.
4. Merging:
   • Unsorted Arrays: Appending elements of array $B$ (size $M$) to array $A$ (size $N$): $O(M)$ time.
   • Sorted Arrays (Two-Pointer Technique): Concurrently traversing both sorted sequences and selecting the smaller candidate element yields a merged sorted array of size $N+M$ in linear time: $O(N + M)$ comparisons and $O(N + M)$ space.

5. Searching Algorithms

A. Linear Search (Sequential Search)

Sequentially evaluates each item in an array from index $0$ to $N-1$ until a target key match occurs or the collection is exhausted.

• Preconditions: None; operates on both sorted and unsorted sequences.
• Best-Case Complexity: $O(1)$ (target matches the very first element).
• Worst-Case Complexity: $O(N)$ (target is at the final index or absent).
• Average-Case Complexity: $O(N)$ (approximately $(N+1)/2$ comparisons).
• Space Complexity: $O(1)$ auxiliary memory.

B. Binary Search (Logarithmic Search)

Operates on the divide-and-conquer paradigm by continuously dividing a sorted search interval in half.

• Preconditions: The array MUST be in sorted order with random-access indexing.
• Algorithm:
  1. Initialize low = 0 and high = N - 1.
  2. Compute mid = low + (high - low) / 2 (preventing arithmetic integer overflow).
  3. If A[mid] == target, return mid.
  4. If target < A[mid], narrow search space: high = mid - 1.
  5. If target > A[mid], narrow search space: low = mid + 1.
  6. Terminate when low > high (target absent).
• Recurrence Relation: $T(N) = T(N/2) + O(1)$. By Master Theorem: $T(N) = O(\log_2 N)$.
• Best-Case Complexity: $O(1)$ (target located at initial midpoint).
• Worst-Case & Average Complexity: $O(\log_2 N)$.
• Space Complexity: Iterative version: $O(1)$; Recursive version: $O(\log N)$ call stack depth.

6. Elementary Sorting Algorithms

A. Bubble Sort (Sinking Sort)

Repeatedly steps through the array, compares adjacent adjacent elements ($A[j]$ and $A[j+1]$), and swaps them if they are in the wrong order. With each outer pass $i$, the largest unsorted element "bubbles up" to its correct terminal position.

• Optimization: An early-exit boolean flag (swapped) stops passes if zero swaps occurred, achieving $O(N)$ best-case time on already-sorted arrays.
• Comparisons: In standard version: $\frac{N(N-1)}{2}$ comparisons.
• Time Complexity: Best: $O(N)$ (optimized); Worst: $O(N^2)$; Average: $O(N^2)$.
• Space Complexity: $O(1)$ auxiliary (in-place).
• Stability: Stable (does not swap identical elements).

B. Selection Sort

Divides the array into a sorted prefix and unsorted suffix. In each pass $i$, it systematically scans the unsorted subarray to find the minimum element, and executes exactly one swap to place it at index $i$.

• Key Characteristic: Minimizes the total number of write operations: executes at most $N-1$ swaps across all passes.
• Comparisons: Exactly $\frac{N(N-1)}{2}$ comparisons under all initial orderings.
• Time Complexity: Best: $O(N^2)$; Worst: $O(N^2)$; Average: $O(N^2)$.
• Space Complexity: $O(1)$ auxiliary (in-place).
• Stability: Unstable (long-distance swaps can reorder identical elements, e.g., sorting [4a, 4b, 2] swaps 4a with 2, placing 4a after 4b).

C. Insertion Sort

Incrementally builds a sorted array one item at a time. For each pass $i$ from $1$ to $N-1$, the element $A[i]$ (the key) is extracted, and preceding elements greater than the key are shifted one slot to the right, inserting the key into its sorted slot.

• Online Property: Can sort streaming inputs as elements arrive dynamically.
• Adaptive Performance: Highly efficient for small inputs ($N < 50$) or nearly-sorted datasets.
• Time Complexity: Best: $O(N)$ (already sorted; 1 comparison per element, 0 shifts); Worst: $O(N^2)$ (reverse sorted); Average: $O(N^2)$.
• Space Complexity: $O(1)$ auxiliary (in-place).
• Stability: Stable (equal elements are not shifted past each other).

7. Comparative Analysis Table of Algorithms

8. Summary & Key Review Takeaways

• Linear data structures arrange elements sequentially; non-linear structures represent hierarchical or networked topologies.
• Big-O ($O$) defines asymptotic upper bounds; Omega ($\Omega$) defines lower bounds; Theta ($\Theta$) denotes asymptotically tight bounds.
• 1D array addresses follow $BA + W \times (i - LB)$. 2D array row-major and column-major address calculations depend on column count $C$ and row count $R$.
• Array insertions and deletions require element shifting, exhibiting $O(N)$ worst-case time complexity.
• Binary search operates in $O(\log_2 N)$ by halving sorted ranges, avoiding linear scans.
• Selection Sort performs $O(N^2)$ comparisons but guarantees $O(N)$ swaps. Insertion Sort is adaptive and stable, exhibiting linear $O(N)$ runtime on nearly-sorted arrays.