Q$5.[4]$ Paul has an algorithm, find$2$D$,$ to find an element $x$ in an $nn$ array $A.$ The algorithm

find$2$D iterates over the rows of A and calls the algorithm arrayFind $($as given below$)$ on each

one, until $x$ is found or it has searched all rows of $A.$ What is the worst$-$case running time of find$2$D

in terms of $n?$ Is this a linear$-$time algorithm? Why or why not?

Algorithm arrayFind$($x$,$ A$)$:

Input: An element $x$ and an n$-$element array, $A.$

Output: The index i such that $x=A[i]$ or $-1$ if no element of $A$ is equal to $x.$

ilarr$0$

while $x=A[i]iilarri+1ido$

$ifx=A[i]$ then

return $i$

else

ilarri$+1$

return $-1$