Arrays, InsertionSort, BigO

Arrays

  • Definition: An array is a data structure that stores a fixed-size sequence of elements of the same data type. Elements are stored in contiguous memory locations, allowing for efficient access and modification.

  • Key Features:

    • Indexing: Access elements via an index, with the first element typically at index 0.

    • Fixed Size: Once an array is created, its size cannot be changed.

    • Efficiency:

      • Access: O(1) time complexity for accessing elements by index.

      • Insertion/Deletion:

        • At the end: O(1)

        • At the beginning or middle: O(n) (requires shifting elements).

    • Common Operations:

      • Traversal: Iterating through all elements.

      • Searching: Linear search (O(n)) or binary search (O(log n)) if the array is sorted.

      • Sorting: Arrays can be sorted using algorithms like Insertion Sort.

Insertion Sort

  • Definition: Insertion Sort is a simple comparison-based sorting algorithm. It builds a sorted array one element at a time by repeatedly picking the next element and inserting it into its correct position among the previously sorted elements.

  • Steps:

    1. Start with the second element in the array (consider the first element as a sorted subarray).

    2. Compare the current element with the elements in the sorted subarray.

    3. Shift elements in the sorted subarray to the right to make space for the current element.

    4. Insert the current element in its correct position.

    5. Repeat for all elements in the array.

  • Time Complexity:

    • Best Case (Already Sorted): O(n)

    • Average/Worst Case: O(n²) (Occurs when the array is sorted in reverse order)

  • Space Complexity: O(1) (In-place sorting)

  • Stability: Yes (Preserves the relative order of equal elements)

Big O Notation

  • Definition: Big O notation is a mathematical notation used to describe the upper bound of an algorithm's time or space complexity in terms of the input size (n). It provides a way to discuss the efficiency of algorithms, particularly their worst-case scenarios.

  • Common Big O Notations:

    • O(1): Constant time. The operation's time remains constant regardless of input size.

    • O(log n): Logarithmic time. Typically occurs in algorithms that halve the problem size at each step (e.g., binary search).

    • O(n): Linear time. The operation's time increases linearly with the input size.

    • O(n log n): Log-linear time. Common in efficient sorting algorithms like merge sort and quicksort.

    • O(n²): Quadratic time. Common in algorithms that involve nested loops over the input (e.g., insertion sort, selection sort).

    • O(2ⁿ): Exponential time. Common in algorithms that solve problems by trying all possible solutions (e.g., recursive solutions to the Traveling Salesman Problem).

    • O(n!): Factorial time. Common in algorithms that generate all possible permutations of the input (e.g., brute force solutions to permutation problems).

  • Importance:

    • Helps in understanding the scalability and performance of algorithms.

    • A lower Big O value usually means a more efficient algorithm, especially for large inputs.