# I.1.2 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$$

<div align="left"><img src="https://1800562540-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LLfCoyr4-Jhfd18nMZ7%2F-LMJUp1WN_leHE3_6ffl%2F-LMJVa1dVWbuWr8tsVdA%2Fimage.png?alt=media&#x26;token=4495a8e2-74d0-4573-9854-426b02a06518" alt=""></div>

### 3-SUM (an example of optimizing your solution)

Original Solution $$O(N^3)$$

```python
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)$$

```python
# 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.*

```python
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:*&#x20;
>
> * 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 ->&#x20;
> * 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$$​.