CS $311$ Challenge Problem $1$ Due: September $17$th$,2024$

Problem $3.$ Asymptotics. Given an array A of n integers, you$$d like to output a two$-$dimensional n $\backslash$times n

array B in which B$[$i$,$ j$]=$ max$($A$[$i$],$ A$[$i $+1],...,$ A$[$j$]$ for each i $<$ j$.$ For i $>=$ j the value of B$[$i$,$ j$]$ can be left

as is$.$

for i $=1,2,...,$ n

for j $=$ i $+1,...,$ n

Compute the maximum of the entries A$[$i$],$ A$[$i $+1],...,$ A$[$j$].$

Store the maximum value in B$[$i$,$ j$].$

$1.$ Find a function f such that the running time of the algorithm is O$($f $($n$)),$ and clearly explain why.

$2.$ For the same function f argue that the running time of the algorithm is also $\backslash$Omega $($f $($n$)).($This establishes

an asymptotically tight bound $\backslash$Theta $($f $($n$)))$

$3.$ Design and analyze a faster algorithm for this problem. You should give an algorithm with runtime

O$($g$($n$)),$ where

limn$->\backslash$infty g$($n$)$

f $($n$)=0$