Sorting
October 13, 2023Nielit STA 17-12-2017
October 13, 2023Sorting
Question 63
|
Consider the following function count, that takes as input a, an array of integers, and N, the size of the array.
Further, let 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?

Further, let 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 N ≥ c, there exists an array of size N for which count_IS ≥ N2/c,
while count_FN ≤ cN |
|
For all N ≥ c, there exists an array of size N for which count_FN ≥ N2/c, while
count_IS ≤ cN |
|
For all N ≥ c, for all arrays of size N, count_FN ≤ count_IS ≤ c × count_FN
|
|
For all N ≥ c, for all arrays of size N, count_FN ≥ N2/c
|
|
None of the above
|
Correct Answer: A
Subscribe
Login
0 Comments