Dark Mode

174 views

2 votes

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