DSC 40B – Theoretical Foundations of Data Science II

Problems tagged with "sorted structure"

Problem #008

Tags: theoretical lower bounds, sorted structure

Consider the same problem as above, except now you may assume that the array is sorted. What is the tight theoretical lower bound for the worst case time complexity of any algorithm which solves this problem?

Solution

\(\Theta(1)\)

Problem #065

Tags: theoretical lower bounds, sorted structure

Suppose \(a\) and \(b\) are two numbers, with \(a \leq b\). Consider the problem of counting the number of elements in an array which are between \(a\) and \(b\); that is, the number of elements \(x\) such that \(a \leq x \leq b\). You may assume for simplicity that both \(a\) and \(b\) are in the array, and there are no duplicates.

Part 1)

What is a tight theoretical lower bound for this problem, assuming that the array is unsorted? State your answer in asymptotic notation as a function of the number of elements in the array, \(n\).

Solution

\(\Theta(n)\).

Since the array is in arbitrary order, we have to at least read all of the elements, taking \(\Omega(n)\) time. This is a tight lower bound, because we can count the number of elements between \(a\) and \(b\) by looping through and checking whether each element is in \([a, b]\) in linear time.

Part 2)

What is a tight theoretical lower bound for this problem, assuming that the array is sorted? State your answer in asymptotic notation as a function of the number of elements in the array, \(n\).

Solution

\(\Theta(\log n)\).

We can do this in worst-case \(\Theta(\log n)\) time with binary search: find the index of \(a\) in worst-case \(\Theta(\log n)\) time; find the index of \(b\) in worst-case \(\Theta(\log n)\) time; and subtract the two indices (and add one) to get the total number of elements between \(a\) and \(b\), inclusive.

There cannot be an algorithm that is better than \(\Theta(\log n)\) in the worst case, so this is a tight lower bound. To see why, recognize that we can solve the query problem (determine True/False if a target \(t\) is in a sorted array) with any algorithm that solves this problem by setting \(a = b = t\). If an algorithm solves this problem in faster than \(\Theta(\log n)\), it will also solve the query problem in faster than \(\Theta(\log n)\), but we saw in class that the query problem has a theoretical lower bound of \(\Theta(\log n)\), so such an algorithm cannot exist.

Problem #197

Tags: sorted structure

A rotated sorted array is an array that is the result of taking a sorted array and moving a contiguous section from the front of the array to the back of the array. For example, the array [5, 6, 7, 1, 2, 3, 4] is a rotated sorted array: it is the result of taking the sorted array [1, 2, 3, 4, 5, 6, 7] and moving the first 4 elements, [1, 2, 3, 4], to the back of the array. Sorted arrays are also rotated sorted arrays, technically speaking, since you can think of a sorted array as the result of taking the sorted array and moving the first 0 elements to the back.

The function below attempts to find the value of the minimum element in a rotated sorted array. It is given the array arr and the indices start and stop which indicate the range of the array that should be searched. One line in the function has been left blank.



import math
def find_minimum_in_rotated_sorted(arr, start, stop):
    """
    Searches arr[start:stop] for the smallest element.
    Assumes arr is a rotated sorted array.
    """
    if stop < start:
        return arr[0]
    if stop == start:
        return arr[start]
    mid = (start + stop) // 2

    if ________________:
        return arr[mid + 1]
    if arr[start] < arr[mid]:
        return find_minimum_in_rotated_sorted(arr, mid, stop)
    else:
        return find_minimum_in_rotated_sorted(arr, start, mid - 1)

What should be filled in the blank line to make this function work correctly?

Solution

5th option: arr[middle] > arr[middle+1]