$3.[10$ points total$]$ This problem was posed by a student in a group discussion. Often when writing code, we see

a double$-$nested loop pattern. In some cases, the inner loop runs a constant number of times. For example:

Algorithm $3.$ Double Loop

Input:array A of n items, some constant k

$1$: function DOUBLE$-$LOOP$($A$)$

$2$: for i $=1$ to n do

$3$: for j $=1$ to k do

$4$: some costly calculation involving only Ai

$5$: some calculation involving Ai and Aj

$6$: return something

$($a$)[5$ points$]$ Using the tightest asymptotic representation, from $\backslash$Theta $,$ O$,$ or $\backslash$Omega $,$ derive the asymptotic time

complexity of the loop above.

$($b$)[5$ points$]$ Suppose you are running this loop on a low$-$powered system, e$.$g$.,$ an Arduino board. What

change could you make to the logic above to speed up the operation, and what overall improvement

would you gain in running time?