Unit 1: Introduction, Arrays, Sorting and Searching

I. Orientation

Data structures organize data for efficient storage and use, while algorithms provide finite, ordered steps for solving problems. This unit begins with arrays because they show how data occupies memory, how operations affect complexity, and why different sorting and searching methods suit different situations.

• Core principle: The best algorithm depends on input size, required operations, available memory, and whether the data is ordered.
• Data organization: A data structure stores values together with relationships or access rules.
• Algorithmic efficiency: Efficiency is mainly evaluated using running time and extra memory as functions of input size.
• Index convention: Unless stated otherwise, array indexing begins at 0.
• Input size: n denotes the number of elements processed by an algorithm.
• Correctness condition: An algorithm must produce the required output for every valid input, not merely run quickly.

II. Basic Concepts and Notations — Foundations of algorithmic reasoning

A data structure is a systematic way to store data, and an algorithm is a finite sequence of unambiguous operations that transforms input into output.

A. Basic concepts and notations

This subsection establishes the symbols and terms used to describe algorithms and data structures.

• Input and output: An algorithm receives input values and produces output values; for example, sorting [4, 2, 1] produces [1, 2, 4].
• Element and index: An element is a stored value, while its index identifies its position; A[2] is the third element of array A.
• Size notation: n commonly represents input size, such as the number of array elements.
• Pseudocode: Pseudocode expresses logic without requiring a particular programming language.
• Operation count: Assignments, comparisons, swaps, and arithmetic operations may be counted to estimate efficiency.
• Correctness: A loop invariant, such as “the first i elements are sorted,” can help prove that an algorithm remains correct during execution.

III. Complexity Analysis — Measuring algorithm performance

Complexity analysis studies how an algorithm’s resources grow as the input size increases. It usually focuses on asymptotic behavior rather than exact machine-dependent timings.

A. Complexity analysis

This subsection explains the two principal resources used to evaluate algorithms.

• Time complexity: Measures the number of basic operations as a function of n; scanning an array once requires approximately n comparisons.
• Space complexity: Measures memory used by the algorithm, including input storage when relevant and auxiliary memory created during execution.
• Best case: The minimum work for an input of size n; linear search finds the target at index 0 after one comparison.
• Worst case: The maximum work; linear search may inspect all n elements.
• Average case: Expected work over an assumed distribution of inputs; a successful linear search often examines about (n + 1) / 2 positions.
• Dominant growth: Constants and lower-order terms are ignored asymptotically, so 3n² + 2n + 1 is treated as quadratic.

B. Time-space trade-off

This subsection describes the choice between faster processing and greater memory use.

• Extra memory for speed: A lookup table can store previously computed results, reducing repeated computation while increasing space usage.
• In-place processing: An algorithm such as selection sort uses only a constant number of temporary variables, giving O(1) auxiliary space.
• Copying for convenience: Merging arrays into a new array is simple and preserves source arrays, but it requires O(n + m) additional space for arrays of lengths n and m.
• Design decision: When memory is limited, an in-place algorithm may be preferred; when speed is critical, additional indexed storage may be justified.

C. Omega notation

This subsection defines the asymptotic lower-bound notation used to express guaranteed growth.

• Formal meaning: f(n) = Ω(g(n)) if there are constants c > 0 and n₀ such that f(n) ≥ c g(n) for every n ≥ n₀.
• Interpretation: Ω(g(n)) states that g(n) is a lower bound on growth.
• Example: Reading every element to compute an array sum is Ω(n) because each of the n values must be examined.
• Caution: Omega notation is not automatically the best-case complexity; it can describe a lower bound applying to all inputs.

D. Theta notation

This subsection defines tight asymptotic bounds.

• Formal meaning: f(n) = Θ(g(n)) when constants c₁, c₂ > 0 and n₀ exist such that 0 ≤ c₁g(n) ≤ f(n) ≤ c₂g(n) for n ≥ n₀.
• Interpretation: Theta notation states that two functions grow at the same asymptotic rate.
• Example: Accessing A[i] in a conventional array is Θ(1) because one address calculation and one memory access are required.
• Relation: If an operation is both Ω(n) and O(n), its tight bound is Θ(n).

E. Big O notation

This subsection defines the asymptotic upper bound used most often for performance limits.

• Formal meaning: f(n) = O(g(n)) if constants c > 0 and n₀ exist such that f(n) ≤ c g(n) for all n ≥ n₀.
• Common classes: Constant O(1), logarithmic O(log n), linear O(n), quadratic O(n²), and exponential O(2ⁿ).
• Example: Two nested loops each running n times perform about n² iterations, giving O(n²).
• Use: Big O gives an upper-growth guarantee; it does not state an exact running time for a particular computer.

IV. Basic Data Structures — Ways to organize data

Basic data structures differ in how elements are related and how operations are performed.

A. Basic data structures

This subsection distinguishes common structures by arrangement and access method.

• Array: Stores elements in contiguous memory and supports direct indexed access.
• Linked list: Stores nodes connected by links; insertion can avoid shifting elements, but indexed access is generally O(n).
• Stack: Follows last-in, first-out order; push and pop operate at the top.
• Queue: Follows first-in, first-out order; insertion occurs at the rear and removal at the front.
• Tree: Represents hierarchical relationships, such as parent and child nodes.
• Graph: Represents general relationships using vertices and edges.
• Selection criterion: Arrays suit direct access, while linked structures suit frequent structural insertion or deletion.

V. Linear Arrays — Contiguous indexed storage

A linear array is an ordered sequence of elements of the same logical type, arranged along one dimension and accessed by index.

A. Linear arrays

This subsection defines the structure and basic access rules of a one-dimensional array.

• Declaration: An array of capacity 5 can be represented as A[0..4].
• Logical order: Elements occupy positions 0, 1, 2, 3, 4; the position determines their sequence.
• Direct access: A[i] can be retrieved without scanning preceding values.
• Capacity and size: Capacity is allocated storage, while size is the number of currently valid elements; these values may differ in dynamic arrays.
• Boundary condition: A valid index satisfies 0 ≤ i < size; accessing A[size] is outside the active range.

B. Memory representation of arrays

This subsection explains how an array index is converted into a memory address.

• Contiguous layout: Array elements occupy consecutive memory locations.
• Address formula: For a zero-based array,
  address(A[i]) = base + i × w, where base is the first element’s address and w is element size in bytes.
• Numeric example: If base = 1000, w = 4, then A[3] begins at 1000 + 3 × 4 = 1012.
• Consequence: Direct address calculation gives array access Θ(1).
• Limitation: Insertion near the beginning requires moving later elements, despite constant-time indexed access.

C. Array traversal

This subsection describes visiting each active array element exactly once.

• Purpose: Traversal supports printing, summing, counting, and updating elements.
• Pseudocode:
  
  TEXT

    for i ← 0 to n - 1
        process A[i]

• Symbols: A is the array, i is the index, and n is the number of active elements.
• Complexity: The loop performs n visits, so time is Θ(n) and extra space is O(1).
• Example use: A sum operation initializes sum = 0 and adds A[i] during each visit.

D. Array insertion

This subsection explains adding an element while preserving array order.

• End insertion: If free capacity exists, placing a value at index n takes Θ(1).
• Middle insertion: To insert x at position p, shift elements from the end toward the right:
  
  TEXT

    for i ← n - 1 down to p
        A[i + 1] ← A[i]
    A[p] ← x
    n ← n + 1

• Shift count: The number of shifts is n - p; inserting at p = 0 shifts all n elements.
• Complexity: Insertion at the beginning or middle is O(n) worst case; insertion at the end is O(1) when capacity is available.
• Condition: The array must have unused capacity or be resized before insertion.

E. Array deletion

This subsection explains removing an element and closing the resulting gap.

• Deletion at position p: Shift each later element one position left:
  
  TEXT

    for i ← p to n - 2
        A[i] ← A[i + 1]
    n ← n - 1

• Shift count: The operation shifts n - p - 1 elements.
• Complexity: Deleting the first element is O(n), while deleting the last active element is O(1).
• Logical deletion: Decreasing n makes the final old value inactive even if its memory cell still contains data.
• Order requirement: Shifting preserves order; replacing the deleted value with the last element is faster but changes order.

F. Array merging

This subsection combines two arrays into one resulting sequence.

• Concatenation: For arrays of lengths n and m, copy the first array followed by the second.
• Result size: The merged array contains n + m elements.
• Complexity: Time is Θ(n + m) because every element is copied; auxiliary space is Θ(n + m) if a new array is created.
• Sorted merging: If both inputs are sorted, compare their front elements and repeatedly copy the smaller one, also requiring Θ(n + m) time.
• Example: Merging [1, 4] and [2, 3] produces [1, 2, 3, 4] through ordered comparisons.

G. Complexity analysis of array operations

This subsection compares the principal costs associated with arrays.

• Indexed access: A[i] is Θ(1) because the address is calculated directly.
• Traversal and searching: Visiting or linearly searching n elements is Θ(n) in the worst case.
• Insertion: Inserting at the end is O(1) with capacity; inserting at the front is O(n).
• Deletion: Removing the final element is O(1); removing the first is O(n).
• Merging: Combining lengths n and m requires Θ(n + m) time.
• Memory cost: A fixed array of n elements uses Θ(n) storage, excluding implementation-specific metadata.

VI. Array Sorting — Ordering stored values

Array sorting rearranges elements into ascending, descending, or another specified order. The algorithms below compare values and modify the array in place.

A. Array sorting

This subsection states the purpose and correctness condition of sorting.

• Sorted condition: An ascending array satisfies A[i] ≤ A[i + 1] for every valid i.
• Benefits: Ordered data supports binary search and simplifies duplicate detection.
• Stability: A stable sort preserves the relative order of records with equal keys.
• In-place property: Bubble, insertion, and selection sort can sort within the original array using O(1) auxiliary space.

B. Bubble sort

This subsection explains repeated adjacent exchanges that move large values toward the end.

• Method: Compare A[j] and A[j + 1]; swap when the left value is larger.
• Pseudocode:
  
  TEXT

    for pass ← 0 to n - 2
        swapped ← false
        for j ← 0 to n - pass - 2
            if A[j] > A[j + 1]
                swap A[j], A[j + 1]
                swapped ← true
        if swapped = false
            break

• Complexity: Worst and average time are O(n²); with the early-stop test, an already sorted array takes O(n).
• Properties: Bubble sort is stable and uses O(1) extra space.

C. Insertion sort

This subsection explains inserting each new element into the sorted prefix before it.

• Method: At iteration i, save A[i] as the key and shift larger prefix values right.
• Pseudocode:
  
  TEXT

    for i ← 1 to n - 1
        key ← A[i]
        j ← i - 1
        while j ≥ 0 and A[j] > key
            A[j + 1] ← A[j]
            j ← j - 1
        A[j + 1] ← key

• Complexity: Best time is O(n) for sorted input; average and worst time are O(n²).
• Properties: It is stable, in-place, and effective for small or nearly sorted arrays.

D. Selection sort

This subsection explains repeatedly selecting the smallest remaining element.

• Method: For position i, find the minimum in A[i..n-1], then swap it with A[i].
• Complexity: The comparisons total approximately n(n - 1)/2, giving Θ(n²) in best, average, and worst cases.
• Space: Selection sort uses O(1) auxiliary space and performs at most n - 1 swaps.
• Property: Ordinary selection sort is generally not stable because a distant minimum may leap over equal elements.

VII. Array Searching — Locating a target value

Searching determines whether a target exists and, if so, returns its position. The appropriate method depends mainly on whether the array is sorted.

A. Array searching

This subsection frames searching as a sequence of comparisons against a target.

• Target notation: x denotes the value being sought, and the result may be an index or a failure marker such as -1.
• Unsorted input: Linear search works without requiring any ordering.
• Sorted input: Binary search uses order to discard half the remaining range after each comparison.
• Performance choice: Sorting may require O(n²) with simple methods but can make repeated searches logarithmic.

B. Linear search

This subsection explains sequentially checking elements from the beginning.

• Pseudocode:
  
  TEXT

    for i ← 0 to n - 1
        if A[i] = x
            return i
    return -1

• Correctness: Every position is checked in order, so a returned index contains x; -1 means no position matched.
• Complexity: Best case is O(1), while worst and unsuccessful cases are O(n).
• Space: Extra space is O(1).
• Use: It is suitable for short or unsorted arrays and for data searched only occasionally.

C. Binary search

This subsection explains repeated halving of a sorted search interval.

• Condition: The array must be sorted in the same order used by comparisons.
• Pseudocode:
  
  TEXT

    low ← 0
    high ← n - 1
    while low ≤ high
        mid ← low + (high - low) // 2
        if A[mid] = x
            return mid
        else if A[mid] < x
            low ← mid + 1
        else
            high ← mid - 1
    return -1

• Symbols: low and high bound the active interval; mid is its midpoint; // denotes integer division.
• Complexity: Each comparison halves the interval, giving O(log n) worst-case time and O(1) iterative space.
• Example: Searching a 16-element array needs at most about log₂16 + 1 = 5 midpoint checks.
• Limitation: Maintaining sorted order makes arbitrary insertion expensive, so binary search is most valuable when searches substantially outnumber updates.