There is an algorithm which compares numbers in an array, and supposedly this time complexity function can be found from it. $n$ is the number of elements in the array.
I believe "show" is synonymous with "prove". But how can I prove this? I'm not particularly well versed in either, but am I supposed to use big O or proof by induction? Or something else entirely? I just do not know where I would start with this.
EDIT: Here is the algorithm. I'm sorry! I didn't know seeing the algorithm itself was essential finding out what kind of proof was needed.
Input $x_1$, $x_2$, $x_3$, $…$, $x_n$ ;
check := true ;
while check = true do
$\phantom{{}++{}}$for i := $1$ to $n-1$ do
$\phantom{{}++++{}}$for j := $i+1$ to $n$ do
$\phantom{{}++++++{}}$if $x_i = x_j$ then
$\phantom{{}++++++++{}}$check := false ;
Output check ;
I don't know a lot about time complexity or this particular function, but my intuition tells me you want to do this by counting. So if $x_1,...,x_n$ are your numbers you must compare $x_1$ to $x_2,...,x_{n}$. Then you have to compare $x_2$ to $x_3,...,x_n$, $x_3$ to $x_4,...,x_n$, and finally $x_{n-1}$ to $x_n$. So you make $(n-1)+(n-2)+...+2+1$ comparisons, which is $(n-1)n/2$ total comparisons. You can figure that out the same way Gauss did. \begin{align*}(n-1)&+(n-2)&+&...+&2\hspace{6mm}+&\hspace{6mm}1&=m\\1\hspace{6mm}&+\hspace{6mm}2&+&...+&(n-2)+&(n-1)&=m\\ n\hspace{6mm}&+\hspace{6mm}n&+&...+&n\hspace{6mm}+&\hspace{6mm}n&=2m \end{align*} $$m=\frac{n(n-1)}{2}.$$