Analysis of Algorithms

Analysis of Algorithms

Question 1. 3-SUM in quadratic time.

Suppose the input array is S[0..n−1]. 3-SUM can be solved in quadratic time on average by inserting each number S[i], and then for each index i and j, checking whether the hash table contains the integer -(S[i]+S[j]). It is also possible to solve the problem in the same time without hash table. The algorithm below first sorts the input array and then tests all possible pairs in a careful order that avoids the need to binary search for the pairs in the sorted list, achieving quadratic time worst-case.

sort(S);
for i = 0 to n - 2 do
    a = S[i];
    start = i + 1;
    end = n - 1;
    while (start < end) do
        b = S[start]
        c = S[end];
        if (a + b + c == 0) then
            output a, b, c;
            // Continue search for all triplet combinations summing to zero.
            // We need to update both end and start together since the array values are distinct.
            start = start + 1;
            end = end - 1;
        else if (a + b + c > 0) then
            end = end - 1;
        else
            start = start + 1;
    end
end

The full description of this algorithm is available in wikipedia.

Question 2. Search in a bitonic array.

A simple solution is to do a linear search. The time complexity of this solution would be O(n).
An efficient solution is based on Binary Search. The idea is to find the bitonic point k which is the index of the maximum element of a given sequence. If the element to be searched is greater than the maximum element return -1, else search the element in both halves. Below is the step by step algorithm on how to do this.

1. Find the bitonic point in the given array, i.e the maximum element in the given bitonic array. This can be done in log(n) time by modifying the binary search algorithm. You can refer to this post on how to do this.
2. If the element to be searched is equal to the element at the bitonic point then print the index of the bitonic point.
3. If the element to be searched is greater than the element at a bitonic point then the element does not exist in the array.
4. If the element to be searched is less than the element at a bitonic point then search for the element in both halves of the array using binary search.

The full description of this algorithm is available in geeksforgeeks.

Question 3. Egg drop.

Version 0: 1 egg and ≤ T tosses.

In this version, you can use a simple iterative traversal of all floors until the egg breaks. If it is broken, then the floor from which we threw this egg is the T floor.

Version 1: ∼1lg(n) eggs and ∼1lg(n) tosses.

This problem is solved by binary search, it just has the necessary complexity.

Version 2: ∼lg(T) eggs and ∼2lg(T) tosses.

For this task we can use exponential search.

Version 3: 2 eggs and ∼2sqrt(n) tosses.

Go iteratively go across floors with incrementing by √N: first visiting 0, then √N, then √2N, etc. Once the egg breaks at stage √kN, iterate across the range (√(k−1)N and √kN one floor at a time.

Version 4: 2 eggs and ≤ c sqrt(T) tosses for some fixed constant c.

The solution to this problem is to throw the eggs exponentially until they break, and then go back to the last point when the thrown egg did not break and iterate to the floor when the egg breaks again.