Question $1.$ Consider the following algorithm.

Algorithm$1$: Secret $($A$[0..$n$-1])$

Data: Input: An array A $[0...$n$-1]$ of n real numbers

for ilarr$0$ to $n-2$ do

for jlarri$+1$ to $n-1$ do

if $A[i]=A[j]$ return false

return true

a$)$ What does this algorithm compute?

b$)$ What is its basic operation?

c$)$ How many times is the basic operation executed?

d$)$ What is the efficiency class of this algorithm?

e$)$ Suggest an improvement or a better algorithm altogether and indicate its efficiency class. If you

cannot do it$,$ try to prove that, in fact, it cannot be done.

Question $2.$ For each of the following pairs of functions; indicate whether the first function of

each of the following pairs has a lower, same, or higher order of growth $($to within a constant

multiple$)$ than the second function.

a$)lo{g}_2^{2}n$ and $lo{g}_2{n}^2$

b$)2^{n-1}$ and $2^n$

Question $3.$ The range of a finite nonempty set of $n$ real numbers $S$ is defined as the difference

between the largest and smallest elements of S$.$ For each representation of S given below,

Indicate the time efficiency classes of these algorithms using the most appropriate notation $,$

$,$ or $).$

An unsorted array

A sorted array

A sorted singly linked list.

Question $4.$

a$)$ What is the big$-$O$,$ c$,$ and $n0$ of $(n^3-n-1)(5n^2+2n-10)$

b$)$ What is the big$-,c$ and $n0$ of $log(n-1)$

CSC$311$: The Design and Analysis of Algorithms

Question $5.$ Order the following functions according to their order of growth, if there are two

equal functions write $=$ :