# Better Enumeration

## Pseudo-Code
The "Better Enumeration" maximum sub-array algorithm is described by the following pseudo-code:
~~~~
BETTER-ENUMERATION-MAX-SUBARRAY(A[1, ..., N])
	maximum sum = -Infinity
	for i from 1 to N
		current sum = 0
		for j from i to N
			current sum = current sum + A[j]
			if current sum > maximum sum
				maximum sum = current sum
				start index = i
				end index = j

	return maximum sum, A[start index, ..., end index]
~~~~

## Theoretical Run-time Analysis
The outer $i$ loop runs from $1$ to $N$, and the inner $j$ loop runs from $i$ to $N$. Inside the inner loop are constant time operations. We can compute the number of iterations of these constant time operations as:

\begin{equation}
\begin{split}
\sum_{i=1}^N \sum_{j=i}^N \Theta(1) & =  \sum_{i=1}^N (N + 1 - i)\cdot \Theta(1) =N(N+1)\cdot \Theta(1) -\frac{1}{2}N(N+1)\cdot \Theta(1) \\
& = \frac{1}{2}N(N+1)\cdot \Theta(1) = \Theta(N^2)
\end{split}
\end{equation}

Thus, the theoritical run-time is $\Theta(N^2)$.

## Experimental Analysis
For a series of array sizes $N$, 10 random arrays were generated and run through the "Better Enumeration" algorithm. The CPU clock time was recorded for each of the 10 random array inputs, and an average run time was computed. Below is the plot of average run time versus $N$ for the "Better Enumeration" algorithm.

<center><font color='red' size="6"></font></center>

A curve fit was applied to the average run time data, which resulted in the following fit equation as a function of $x$ standing in for $N$:

$$y = 5.48722 * 10^{-8} * x^{2} + 1.42659 * 10^{-4} * x - 7.776 * 10^{-1}$$

The fit curve for the plotted data has the same degree as the theoretical runtime of $\theta(N^{2})$ so the experimental appears to match the theoretical runtime. 

Based on the average run time data curve fit, we would expect the "Better Enumeration" to be able to process the following number of elements in the given amount of time:

|    Time    | Max Input Size |
|:----------:|:--------------:|
| 10 seconds |      12775     |
| 30 seconds |      22419     |
| 60 seconds |      32006     |

7c8f8dbe13b0cb2f8df952c15d7d2aee16d0f63e
ipynb
Jupyter Notebook
better-enumeration/betterEnumeration.ipynb
OSU-CS-325/Project_One_MSS
73ecbf2eeb1c6b35e3d63f3054649b26cb7c7d0d
MIT
better-enumeration/betterEnumeration.ipynb
OSU-CS-325/Project_One_MSS
73ecbf2eeb1c6b35e3d63f3054649b26cb7c7d0d
MIT
better-enumeration/betterEnumeration.ipynb
OSU-CS-325/Project_One_MSS
73ecbf2eeb1c6b35e3d63f3054649b26cb7c7d0d
MIT
Qwen/Qwen-72B
1. YES
2. YES