I.1.2 Analysis of Algorithms

Algorithm I Week 1: Analysis of Algorithms

Recap

Observations -> Mathematical Models -> Order-of-Growth

Observations RunTime -> $ax^b$

Mathematical Models -> f(N)

Order $1, \lg N, N, N\lg N, N^2, N^3, 2^N$

3-SUM (an example of optimizing your solution)

Original Solution $O(N^3)$

for i in range(N):
    for j in range(i+1, N):
        for k in range(j+1, N):
            if arr[i] + arr[j] + arr[k] == 0:
                # do something
            k += 1
        j += 1
    i += 1

Runtime: $C^N_3 = \frac{1}{6} N^3$

Improvements $O(N^2\lg N)$

# sort array
# for pair(i, j):
#    do binary search for -(i+j)

Types of analyses

• Best Case

• Worst Case

• Average Case

Establish "difficulty" of a problem

• ~$N$(approximate model)

• $\Omega(N)$ (Θ(N2) and larger, used to develop lower bounds)

• $O(N)$ (Θ(N2) and smaller, used to develop upper bounds) (often misused)

• $\Theta(N)$ (asymptotic order of growth, used to classify algorithms)

When lower bound equals upper bound (to within a constant factor), it is optimal. The one we often times use to represent the runtime of a model is actually the tilde notation (Big Oh is a misuse, according to prof. Robert Sedgewick )

Interview Questions

1. 3-SUM in quadratic time. Design an algorithm for the 3-SUM problem that takes time proportional to n2 in the worst case. You may assume that you can sort the nn integers in time proportional to n2 or better.

Note: these interview questions are ungraded and purely for your own enrichment. To get a hint, submit a solution.

for i in range(N):
    j, k = i+1, N-1
    while j<k:
        sum = arr[i]+arr[j]+arr[k]
        if sum==0: return (i,j,k)            
        elif sum<0:j++
        else: k--

2. Search in a bitonic array. An array is bitonic if it is comprised of an increasing sequence of integers followed immediately by a decreasing sequence of integers. Write a program that, given a bitonic array of nn distinct integer values, determines whether a given integer is in the array.

• Standard version: Use ∼3lg⁡n cmpares in the worst case.

• Signing bonus: Use ∼2lg⁡n compares in the worst case (and prove that no algorithm can guarantee to perform fewer than ∼2lg⁡n compares in the worst case).

monotonic side lgn + bitonic side 2*lgn

see search_bitonic.py

Egg drop. Suppose that you have an n-story building (with floors 1 through n) and plenty of eggs. An egg breaks if it is dropped from floor T or higher and does not break otherwise. Your goal is to devise a strategy to determine the value of T given the following limitations on the number of eggs and tosses:

• Version 0: 1 egg, ≤T tosses.

• Version 1: ∼1lg⁡n eggs and ∼1lgn tosses.

• Version 2: ∼lg⁡T eggs and ∼2lgT tosses.

• Version 3: 2 eggs and ∼2n​ tosses.

• Version 4: 2 eggs and ≤cT​ tosses for some fixed constant cc.

Hints:

• Version 0: sequential search.

• Version 1: binary search.

• Version 2: find an interval containing $T$ of size $\leq 2T$, then do binary search.

  • 0, 2, 4, 8, 16, 32 -> 16, +2, +4, +8, +16 -> 24, +2, +4, +8 -> 28, +2, +4 -> 30, 31

  • 0, 2, 4, 8, 16, 32 .. T ->

• Version 3: find an interval of size $n$​, then do sequential search. Note: can be improved to $∼2n$​ tosses.

  • for i in range(1, n, step = ceil(sqrt(n))): if break: for j in range(n-step, n)

• Version 4: $1+2+3+…+t∼\frac{1}{2}t^2$. Aim for $c=2\sqrt2$​.