# Topic 1 Writing Exercise
###### Lucas, Sean, Will, Bryce

## Exercise 1

a. theta(1) when c < 1:
- take the limit of g(n)/1 to infiniti
- = lim(sum of c^i from 0 to n)
- from infinite geometric series = 1/1-c
- so for c<1 the limit is constant

b. theta(n) when c = 1:
- if c = 1 then g(n) = 1 + 1^1 + 1^2 + ... + 1^n = 1 + n = $\Theta(n)$

c. theta(c^n)
- because $g(n) = 1 + c + c^2 +... + c^n$, when c > 1 the c^n term will dominate the whole expression for big n
- thus, by multiplying by different constants, you can make c^n lower or upper bound of g(n)
- eg.

## Exercise 2
### Part A
The running time would be $O(n^3)$. The nested loops give $\Omega(n^2)$, however the line "Add up the array entries A[i] through A[j]" gives another factor of n because for all $i<n/4$ and all $j>3n/4$ this line loops through at least half of A, which gives at least $1/4 * 1/4 * 1/2 * n = 1/32 * n$ which is just n, which gives $\Omega(n^3)$. Because all other parts of the algorithm are constant, we have $O(n^3)$. Therefore we have $\Theta(n^3)$.

### Part B

B = new int[n][n] array
B[1,1] = A[1]
For j = 2,3, .., n:
   B[1,j] = B[1,j-1] + A[j]

For i = 2,3, .., n:
   For j = i,i+1, .., n:
      B[i,j] = B[i-1,j] - A[i-1]

Return B

This has runtime $O(n^2)$, which is asymptotically better than $O(n^3)$.

## Exercise 3
### Part A
First go to rung n/2, and drop. If jar breaks, drop from rung n/4. If it does not break, drop from rung 3n/4. Continue this pattern where
we drop from a rung and go to one halfway between the current and previous. (Binary Search)

### Part B
You would have to start at rung 0 and work way up to rung n. When jar breaks you know highest one is one below current rung.
Runtime would be $O(n)$.

### Part C
* Start with rung $\sqrt{n}$. Drop the jar and see if it breaks.
* If it does break, go to the lowest and begin dropping. If it does not break then rung 0 then move up one until the jar breaks, when it does the rung before will be the highest.
* If it does not break, move up $\sqrt{n}$ rungs and continue the drop cycle.
* When jar breaks, move down $\sqrt{n}$ rungs and test each individual rung. When the jar breaks again we know that the highest is the rung one below the current rung.

Running time would be $O(\sqrt{n})$.