$1.(10$ pts$)$ Prefix$-$Sum Problem: Given an array A of integers, is there a sub$-$array of

A such that if we add all the elements of the sub$-$array, we get a sum of zero? By

sub$-$array, we mean a contiguous sub$-$array.

Naive Brute Force Algorithm $($Pseudocode$)$:

for i $=1$ to n $\{$

for j $=$ i to n $\{$

sum $=$ A$[$i$]+$ A$[$i $+1]+...+$ A$[$j$]$

if sum $==0$ return true

$\}$

$\}$

return false

Derive the runtime of the above algorithm in detail and determine its Big$-$O upper

bound. You must show the derivation of the end result. Simply stating the final

answer without any derivation steps will result in zero points