Consider the following function $\textsf{count},$ that takes as input $a,$ an array of integers, and $\textsf{N}$, the size of the array.
int count(int a[], int N) {
int i, j, count_FN;
count_FN = 0;
for (i=1 ; i<N ; i++) {
j=i-1 ;
while (a[j]>a[i]) {
count_FN++;
j--;
}
}
return count_FN;
}
Further, let $\textsf{count_IS}$ be the number of comparisons made by the insertion sort algorithm on the array $a$.
Which of the following statements is TRUE for some constant $c?$
- For all $\textsf{N} \geq c$, there exists an array of size $\textsf{N}$ for which $\textsf{count_IS} \geq \textsf{N}^2 / c$, while $\textsf{count_FN} \leq c \textsf{N}$
- For all $\textsf{N} \geq c$, there exists an array of size $\textsf{N}$ for which $\textsf{count_FN} \geq \textsf{N}^2 / c$, while $\textsf{count_IS}\leq c \textsf{N}$
- For all $\textsf{N} \geq c$, for all arrays of size $\textsf{N, count_FN} \leq \textsf{count_IS} \leq c \times \textsf{count_FN}$
- For all $\textsf{N} \geq c$, for all arrays of size $\textsf{N, count_FN} \geq \textsf{N}^2 / c$
- None of the above
