in Algorithms recategorized by
120 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
in Algorithms recategorized by
by
120 views

Please log in or register to answer this question.

Answer:

Related questions