COSC $5313$

Analysis of Algorithms

Assignment $1$

Due: $23$:$59$:$00$pm$,01/21/2024$

If $f(n)=2n2+n+10$ and $g(n)=n2,$ please show $f(n)=(g(n)).($Hint: you need to find $c_1,c_2,$ and $n_o$ to make $($:$c_{1}g(n)f(n)c_{2}g(n)\}(0\mathrm{.}6$ points$)$

$(1)$ If the input is an increasing sorted array with $n$ elements, what is the time complexity, $T(n),$ of Linear Search for the maximum element?

$(2)$ If the input is a decreasing sorted array with $n$ elements, what is the time complexity, $T(n),$ of Binary Search for the maximum element? $(0\mathrm{.}8$ points$)$

What is the big $O$ notation of the following program $($please show detailed steps for full credits$)$:

for $($int $j=i$;$ji=1$;$i$