recategorized by
420 views
2 votes
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?$ 

  1. 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}$
  2. 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}$
  3. 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}$
  4. For all $\textsf{N} \geq c$, for all arrays of size $\textsf{N, count_FN} \geq \textsf{N}^2 / c$
  5. None of the above
recategorized by

Please log in or register to answer this question.

Answer:

Related questions

1 votes
1 votes
1 answer
1
admin asked Sep 1, 2022
800 views
Consider the problem of sorting $n$ single digit integers (base $10$). This problem can be solved in time$O(n \log n)$ but not $O(n \log \log n)$$O(n \log \log n)$ but no...