Unit 1: Introduction, Arrays, Sorting and Searching - Subjective Questions

An algorithm is a finite sequence of well-defined instructions used to solve a problem or compute a result.

Characteristics of a good algorithm:

• Input: It accepts zero or more clearly specified inputs.
• Output: It produces at least one well-defined output.
• Definiteness: Every instruction is precise and unambiguous.
• Finiteness: It terminates after a finite number of steps.
• Effectiveness: Each operation is simple enough to be performed in finite time.
• Correctness: It produces the expected output for every valid input.
• Generality: It solves all instances of the intended problem class.
• Efficiency: It uses time and memory economically.

Common representation notations:

• Natural language: Steps are written in ordinary language.
• Pseudocode: Language-independent, structured instructions are used.
• Flowcharts: Graphical symbols represent control flow.
• Programming languages: The algorithm is implemented as executable code.

Complexity analysis measures the resources required by an algorithm as a function of input size .

Time complexity:

• Describes how the number of elementary operations grows with .
• It is generally expressed using asymptotic notation.
• For example, linear search may inspect all elements, so its worst-case time complexity is .

Space complexity:

• Describes how much memory an algorithm requires as grows.
• It includes input storage and auxiliary memory used during execution.
• For example, an in-place selection sort uses auxiliary space.

Difference:

• Time complexity concerns execution effort.
• Space complexity concerns memory consumption.

An algorithm can be faster but consume more memory, or use less memory while taking more time. Therefore, both measures should be considered when selecting an algorithm.

The time-space trade-off is the principle that an algorithm can often reduce its execution time by using additional memory, or reduce its memory usage by performing additional computation.

Using space to save time:

• A lookup table stores previously computed results.
• A hash table can support average-case searching but requires extra memory.
• Merging two sorted arrays into a third array takes time and additional space.

Using time to save space:

• An in-place algorithm reuses the input array instead of creating another array.
• Recomputing values when needed avoids storing them, but increases execution time.
• Selection sort uses only auxiliary space, although its time complexity is .

The preferred trade-off depends on system constraints. Memory-limited systems favor space-efficient algorithms, while performance-critical systems may use more memory to reduce execution time.

Let represent an algorithm's resource usage and let be a positive comparison function.

Big O notation:

if there exist constants and such that

It gives an asymptotic upper bound.

Omega notation:

if there exist constants and such that

It gives an asymptotic lower bound.

Theta notation:

if there exist constants and such that

It gives a tight asymptotic bound. Thus, Theta notation applies when the same function bounds both above and below.

Given

For , both and are no greater than . Therefore,

Thus, with and .

Also,

Thus, with and .

Since has both an upper and a lower bound proportional to ,

The lower-order terms and and the constant coefficient do not affect the asymptotic growth rate. The dominant term is .

A data structure is a method of organizing and storing data so that it can be accessed and modified efficiently.

Classification:

• Primitive data structures: Basic built-in types such as integers, characters, floating-point values, and Boolean values.
• Non-primitive data structures: Structures constructed from primitive types.
• Linear data structures: Elements are arranged sequentially. Examples include arrays, linked lists, stacks, and queues.
• Non-linear data structures: Elements form hierarchical or network relationships. Examples include trees and graphs.
• Static structures: Their size is usually fixed before execution or allocation. Arrays are commonly static.
• Dynamic structures: Their size can grow or shrink during execution. Linked structures are typical examples.
• Homogeneous structures: All elements have the same data type.
• Non-homogeneous structures: Elements may have different data types.

An array is a linear, homogeneous data structure whose elements occupy contiguous memory locations and are accessed through indices.

A linear array is a finite ordered collection of elements of the same data type stored in contiguous memory locations and identified by a common name and an index.

Characteristics:

• Elements are homogeneous.
• Memory locations are contiguous.
• Each element has a unique index.
• The size is normally fixed when the array is created.
• Direct or random access is supported.

Advantages:

• Accessing an element by index takes time.
• Traversal is simple and cache-friendly.
• Arrays have little per-element storage overhead.
• They are suitable for tables, matrices, and implementing other data structures.

Limitations:

• A fixed-size array cannot easily grow or shrink.
• Insertion and deletion in the middle require shifting elements.
• A large contiguous block of memory may be difficult to allocate.
• Allocating excess capacity wastes memory, while insufficient capacity causes overflow or requires reallocation.

Let be the base address, be the size of each element in bytes, and be the lower bound.

One-dimensional array:

For an element ,

For a zero-based array, , so

Two-dimensional array in row-major order:

For with row lower bound , column lower bound , and columns,

Two-dimensional array in column-major order:

If the array has rows,

Row-major order stores every element of a row consecutively, whereas column-major order stores every element of a column consecutively.

Array traversal is the process of visiting every element of an array, usually once, to read, display, update, or process it.

Pseudocode:

TRAVERSE(A, n)
    for i <- 0 to n - 1
        process A[i]

The loop executes times. If processing one element takes constant time, the total running time is

Therefore:

• Best-case time: when every element must be visited.
• Worst-case time: .
• Auxiliary space: because only an index and a constant amount of temporary storage are required.

Sequential traversal also benefits from spatial locality because adjacent array elements are stored in adjacent memory locations.

To insert an element at position , the elements from onward must be shifted one position to the right. The array must have unused capacity, and must be a valid insertion position.

Pseudocode:

INSERT(A, n, capacity, p, item)
    if n = capacity
        report overflow
    if p < 0 or p > n
        report invalid position
    for i <- n - 1 downto p
        A[i + 1] <- A[i]
    A[p] <- item
    n <- n + 1

Complexity analysis:

• Insertion at the end requires no shifting and takes time when capacity is available.
• Insertion at the beginning shifts all elements and takes time.
• Insertion at an arbitrary position takes time in the worst case.
• The algorithm uses auxiliary space.

The operation preserves the order of all existing elements.

To delete the element at position , all elements after that position are shifted one place to the left to close the gap.

Pseudocode:

DELETE(A, n, p)
    if n = 0
        report underflow
    if p < 0 or p >= n
        report invalid position
    item <- A[p]
    for i <- p to n - 2
        A[i] <- A[i + 1]
    n <- n - 1
    return item

Necessary conditions:

• The array must not be empty.
• The deletion index must lie between and .

Complexity analysis:

• Deleting the last element takes time.
• Deleting the first element takes time because elements are shifted.
• The worst-case and average-case complexities are .
• The auxiliary space complexity is .

Logical deletion reduces the number of valid elements but does not normally reduce the allocated physical capacity of a static array.

Two sorted arrays can be merged by maintaining one index for each input array and repeatedly selecting the smaller current element.

Pseudocode:

MERGE(A, n, B, m)
    i <- 0, j <- 0, k <- 0
    create C of size n + m
    while i < n and j < m
        if A[i] <= B[j]
            C[k] <- A[i]
            i <- i + 1
        else
            C[k] <- B[j]
            j <- j + 1
        k <- k + 1
    copy remaining elements of A into C
    copy remaining elements of B into C
    return C

Each element is copied exactly once. Therefore,

The output array requires additional space. The merge is stable when equal elements from the first array are selected before equal elements from the second array.

Complexities of common array operations:

• Indexed access: because the address is calculated directly.
• Traversal: because every element is visited.
• Linear search: Best case ; average and worst cases .
• Binary search: Best case and worst case , but it requires sorted data.
• Insertion at the end: when free capacity exists.
• Insertion at the beginning or middle: due to shifting.
• Deletion at the end: .
• Deletion at the beginning or middle: due to shifting.
• Bubble, insertion, and selection sorting: in the general worst case.
• Merging two sorted arrays: for arrays of sizes and .

These results follow from contiguous storage: it enables constant-time indexed access but requires movement of subsequent elements when positions are inserted or removed.

Bubble sort repeatedly compares adjacent elements and swaps them when they are in the wrong order. After each pass, the largest unsorted element moves to its final position.

For , the first pass performs:

• Compare and :
• Compare and :
• Compare and :

The value is now in its final position.

The number of comparisons in the unoptimized version is

Complexities:

• Best case with an early-termination flag: .
• Average case: .
• Worst case: .
• Auxiliary space: .

Bubble sort is stable when only strictly out-of-order elements are swapped, and it is in-place.

Insertion sort maintains a sorted prefix and inserts each new element into its correct position within that prefix.

Trace for :

• Insert into : .
• Insert into : .
• Insert into : .

Pseudocode idea: Select as the key, shift larger elements of the sorted prefix to the right, and place the key in the resulting gap.

Complexities:

• Best case for an already sorted array: .
• Average case: .
• Worst case for reverse order: .
• Auxiliary space: .

Insertion sort is stable, in-place, and adaptive. It is particularly useful for small arrays, nearly sorted arrays, and as a finishing method inside more advanced sorting algorithms.

Selection sort divides the array into sorted and unsorted regions. During each pass, it finds the minimum element in the unsorted region and swaps it with the first unsorted element.

For an array of size , the numbers of comparisons in successive passes are

Hence, the total number of comparisons is

At most one swap occurs per pass, so the algorithm performs at most swaps.

Properties:

• Best-case time: .
• Average-case time: .
• Worst-case time: .
• Auxiliary space: .
• It is in-place.
• Standard selection sort is generally not stable, because a swap may change the order of equal elements.
• It is not adaptive, since it performs the same number of comparisons even when the array is already sorted.

It is useful when minimizing the number of writes is more important than minimizing comparisons.

Bubble sort:

• Best time with optimization: .
• Average and worst time: .
• Stable, in-place, and adaptive with an exchange flag.
• May perform many swaps.

Insertion sort:

• Best time: .
• Average and worst time: .
• Stable, in-place, and adaptive.
• Performs well for small or nearly sorted inputs.

Selection sort:

• Best, average, and worst time: .
• In-place but generally not stable or adaptive.
• Performs only swaps, fewer than bubble sort in many cases.

All three use auxiliary space. Insertion sort is normally the most practical of the three for small or nearly sorted arrays. Selection sort is preferred when writes are expensive. Bubble sort is mainly useful for teaching adjacent-exchange sorting and detecting already sorted input with a simple flag.

Linear search examines array elements sequentially until the target is found or the array ends.

Pseudocode:

LINEAR_SEARCH(A, n, key)
    for i <- 0 to n - 1
        if A[i] = key
            return i
    return -1

Complexity analysis:

• Best case: The key is at the first position, requiring one comparison, so the time is .
• Worst case: The key is at the final position or absent, requiring comparisons, so the time is .
• Average case: For a successful search with equally likely positions, the expected comparisons are

which is .

• Auxiliary space: for the iterative version.

Linear search works on both sorted and unsorted arrays and is suitable for small collections or infrequent searches.

Binary search locates a key in a sorted array by repeatedly comparing it with the middle element and discarding half of the remaining search interval.

Trace:

• Initial interval: indices to . Middle index is , containing .
• Since , continue with indices to .
• Middle index is , containing .
• The key is found at index .

After unsuccessful reductions, the remaining search space is approximately

The process stops when this value becomes :

Therefore, the worst-case time complexity is . The best-case time is . Iterative binary search uses auxiliary space, while a recursive implementation uses stack space.

Linear search:

• Works with sorted or unsorted data.
• Checks elements sequentially.
• Best-case time is ; average and worst-case times are .
• It is simple and suitable for small arrays, unsorted data, and one-time searches.
• It can also be applied to structures without efficient random access.

Binary search:

• Requires the data to be sorted.
• Repeatedly halves the search interval.
• Best-case time is ; worst-case time is .
• It is suitable for large sorted arrays and repeated searching.
• It relies on efficient access to the middle element, which arrays provide in time.

Sorting only to perform a single search may cost more than linear search. However, when many searches are required, the one-time sorting cost can be justified by the faster searches.