Java Progtramming

Task A$.$ Implement the three algorithms in Section $1\mathrm{.}4$ in Zybooks:

$$ MaxsubSlow $($Figure $1\mathrm{.}4\mathrm{.}2)$

$$ MaxsubFaster $($Figure $1\mathrm{.}4\mathrm{.}3)$

$$ MaxsubFastest $($Figure $1\mathrm{.}4\mathrm{.}4)$

Note that, for all three algorithms, A must contain both positive and negative numbers.

Note: S is a list of numbers, not a variable. Si denotes the i$-$th element, which will contain the prefix sum of A$[$i$]($i$.$e$.$ the sum of all elements in A up to A$[$i$]).$ The first element, S$0,$ is given a value of $0$ because prefix sum of A$[0]$ is $0,$ since A$[0]$ does not exist.

Note: M is a list of numbers, not a variable. Mi denotes the i$-$th element, which is the prefix maximum for A$[$i$]($i$.$e$.$ the largest subarray of A that can be yielded using only elements up to A$[$i$]).$ The first element, M$0,$ is given a value of $0$ because the prefix maximum of A$[0]$ is $0,$ since A$[0]$ does not exist.

Task B$.$ For each algorithm $,$ perform experiments with $10$ different values for n$,$ and measure the running time $($i$.$e$.$ the number of primitive operations, not the system runtime$).$ Select appropriate n values so the running time is measurable and the change in running time is meaningful. Once you have yielded the runtimes, use the tables below to determine which of the following functions best approximates the running time for each algorithm: n$,$ n$2,$ or n$3.$

Hint: For each value of n$,$ calculate the ratio between the algorithm$$s running time and the function. As n grows infinitely large, the function whose ratio converges to a nonzero value closest to $1$ will be the best approximation.

n T$1($n$)$

MaxsubSlow T$1($n$)/$n T$1($n$)/($n$2)$ T$1($n$)/($n$3)$

n$$infinite Predict this:

n T$2($n$)$

MaxsubFaster T$2($n$)/$n T$2($n$)/($n$2)$ T$2($n$)/($n$3)$

n$$infinite Predict this:

n T$3($n$)$

MaxsubFastest T$3($n$)/$n T$3($n$)/($n$2)$ T$3($n$)/($n$3)$

n$$infinite Predict this:

Based on the experimental data, which of the three functions $($n$,$ n$2,$ or n$3)$ is the best estimation of the time complexity T$($n$)$ of each algorithm?

Answer:

T$1($n$)=\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_.$

T$2($n$)=\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_.$

T$3($n$)=\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_$