Algorithmic Strategies Exercise Solutions | KalviGavani

Linear search checks each element in the list one by one from the beginning until the target is found or the list ends.

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i    # Found: return index
    return -1           # Not found

# Example
numbers = [34, 12, 56, 78, 23, 9]
print(linear_search(numbers, 56))  # 2 (found at index 2)
print(linear_search(numbers, 99))  # -1 (not found)

Time complexity:

• Best case: O(1) — target is at the first position.
• Worst case: O(n) — target is at the last position or not present.
• Average case: O(n) — target is somewhere in the middle.

Linear search works on both sorted and unsorted lists but is slow for large datasets.

Binary search works on a sorted list by repeatedly dividing the search interval in half. It compares the target with the middle element and eliminates half the list each time.

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2

        if arr[mid] == target:
            return mid           # Found: return index
        elif arr[mid] < target:
            low = mid + 1        # Search right half
        else:
            high = mid - 1       # Search left half

    return -1  # Not found

# Example (list must be sorted)
numbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(numbers, 23))  # 5
print(binary_search(numbers, 7))   # -1

Why binary search is faster:

• Linear search checks n elements in the worst case.
• Binary search checks at most log₂(n) elements.
• For 1,000,000 elements: linear search may need 1,000,000 comparisons; binary search needs at most 20 comparisons.

Prerequisite: The list must be sorted before binary search can be applied.

Bubble sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. After each pass, the largest unsorted element "bubbles up" to its correct position.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:  # Optimisation: stop if no swaps
            break
    return arr

Trace through: [5, 3, 8, 1]

Pass 1:

• Compare 5, 3 → swap → [3, 5, 8, 1]
• Compare 5, 8 → no swap → [3, 5, 8, 1]
• Compare 8, 1 → swap → [3, 5, 1, 8] (8 is in correct position)

Pass 2:

• Compare 3, 5 → no swap → [3, 5, 1, 8]
• Compare 5, 1 → swap → [3, 1, 5, 8] (5 is in correct position)

Pass 3:

• Compare 3, 1 → swap → [1, 3, 5, 8] (3 is in correct position)

Selection sort divides the list into sorted and unsorted portions. In each pass, it finds the minimum element in the unsorted portion and swaps it with the first unsorted element.

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

Trace through: [64, 25, 12, 22, 11]

Pass 1: Find min in [64, 25, 12, 22, 11] → 11 at index 4. Swap with index 0 → [11, 25, 12, 22, 64]

Pass 2: Find min in [25, 12, 22, 64] → 12 at index 2. Swap with index 1 → [11, 12, 25, 22, 64]

Pass 3: Find min in [25, 22, 64] → 22 at index 3. Swap with index 2 → [11, 12, 22, 25, 64]

Pass 4: Find min in [25, 64] → 25 at index 3. No swap needed → [11, 12, 22, 25, 64]

Insertion sort builds a sorted list by taking each element and inserting it into its correct position in the already-sorted portion.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

# Example
numbers = [12, 11, 13, 5, 6]
print(insertion_sort(numbers))  # [5, 6, 11, 12, 13]

Trace through: [12, 11, 13, 5]

• i=1: key=11, shift 12 right → [12, 12, 13, 5], insert 11 → [11, 12, 13, 5]
• i=2: key=13, no shifts needed → [11, 12, 13, 5]
• i=3: key=5, shift 13, 12, 11 right → [11, 11, 12, 13], insert 5 → [5, 11, 12, 13]

Best-case time complexity: O(n) This occurs when the list is already sorted. Each element only needs one comparison (no shifting), so the inner while loop runs zero times per element.

Worst-case time complexity: O(n²) This occurs when the list is reverse sorted. Each new element must be compared with all previous elements and shifted to the beginning.

Big O notation describes the upper bound (worst-case) time complexity of an algorithm as a function of input size n. It focuses on the dominant term and ignores constants and lower-order terms.

Examples:

• O(1): arr[0] — accessing any element by index takes constant time regardless of array size.
• O(log n): Binary search on 1,000,000 elements needs at most 20 comparisons.
• O(n): Linear search on 1,000 elements needs at most 1,000 comparisons.
• O(n²): Bubble sort on 100 elements needs up to 100×99/2 = 4,950 comparisons.
• O(n log n): Merge sort on 1,000 elements needs about 1,000 × 10 = 10,000 operations.

Simplification rule: 3n² + 5n + 7 → O(n²) (keep dominant term, drop constants).

Binary search is an efficient algorithm for finding an element in a sorted list. It works by repeatedly dividing the search interval in half.

Algorithm: 1. Set low = 0 and high = len(arr) - 1. 2. While low <= high: a. Calculate mid = (low + high) // 2. b. If arr[mid] == target, return mid (found). c. If arr[mid] < target, set low = mid + 1 (search right half). d. If arr[mid] > target, set high = mid - 1 (search left half). 3. If the loop ends, return -1 (not found).

Python implementation:

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

# Example
numbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(numbers, 23))  # 5
print(binary_search(numbers, 72))  # 8
print(binary_search(numbers, 7))   # -1

Trace: searching for 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]

Only 3 comparisons for a list of 10 elements!

Comparison: Linear search vs Binary search

Merge sort is a divide-and-conquer algorithm that recursively splits the list into halves, sorts each half, and then merges the sorted halves.

Algorithm: 1. Divide: Split the list into two halves. 2. Conquer: Recursively sort each half. 3. Merge: Combine the two sorted halves into a single sorted list.

Python implementation:

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result

# Example
numbers = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(numbers))  # [3, 9, 10, 27, 38, 43, 82]

Trace: [38, 27, 43, 3, 9, 82, 10]

Time complexity:

• Best case: O(n log n)
• Average case: O(n log n)
• Worst case: O(n log n)

Merge sort always divides the list into halves (log n levels) and merges n elements at each level, so the time complexity is consistently O(n log n).

Space complexity: O(n) — requires temporary arrays for merging.

Advantages:

• Consistent O(n log n) performance regardless of input.
• Stable sort (preserves order of equal elements).
• Suitable for large datasets and linked lists.

Disadvantages:

• Requires O(n) extra memory.
• Slower than insertion sort for very small lists.

Bubble Sort — Python implementation:

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

print(bubble_sort([5, 1, 4, 2, 8]))  # [1, 2, 4, 5, 8]

Selection Sort — Python implementation:

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

print(selection_sort([5, 1, 4, 2, 8]))  # [1, 2, 4, 5, 8]

Insertion Sort — Python implementation:

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

print(insertion_sort([5, 1, 4, 2, 8]))  # [1, 2, 4, 5, 8]

When to use which:

• Bubble sort: Educational purposes; rarely used in practice.
• Selection sort: When memory writes are costly (minimum swaps); small datasets.
• Insertion sort: Nearly sorted data; small datasets; as part of more advanced algorithms (like Timsort).

Big O notation describes the upper bound (worst-case) growth rate of an algorithm's time or space requirements as a function of input size n. It focuses on the dominant term and ignores constants and lower-order terms.

Rules for determining Big O:

1. Drop constants: O(3n) → O(n); O(2n²) → O(n²) 2. Drop lower-order terms: O(n² + n) → O(n²); O(n log n + n) → O(n log n) 3. Keep the dominant term: For large n, n² dominates n, which dominates log n, which dominates 1.

Common Big O categories (from fastest to slowest):

Determining time complexity from code:

Example 1 — Single loop: O(n)

def print_items(n):
    for i in range(n):       # Runs n times
        print(i)
# Time complexity: O(n)

Example 2 — Nested loop: O(n²)

def print_pairs(n):
    for i in range(n):          # Runs n times
        for j in range(n):      # Runs n times for each i
            print(i, j)
# Time complexity: O(n × n) = O(n²)

Example 3 — Halving loop: O(log n)

def halve(n):
    while n > 1:
        n = n // 2    # Halves n each step
        print(n)
# Time complexity: O(log n)

Example 4 — Sequential statements: O(n²)

def combined(n):
    for i in range(n):       # O(n)
        print(i)
    for i in range(n):       # O(n²)
        for j in range(n):
            print(i, j)
# Time complexity: O(n) + O(n²) = O(n²)
# Drop the lower-order term O(n)

Example 5 — Binary search: O(log n)

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:           # Halves search space each step
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1
# Time complexity: O(log n) — search space halves each iteration

Merge sort is a divide-and-conquer sorting algorithm that: 1. Divides the list into two halves. 2. Recursively sorts each half. 3. Merges the two sorted halves.

Step-by-step trace: sorting [6, 5, 3, 1, 8, 7, 2, 4]

Merge step detail: merging [1, 3, 5, 6] and [2, 4, 7, 8]

Comparison: Merge Sort vs Bubble Sort

Merge sort is significantly faster for large datasets (O(n log n) vs O(n²)), but requires extra O(n) memory. Bubble sort is simple but impractical for large lists.