Algorithm : Nuclear Quiz 2

Which of the following is true about insertion sort?

I. Insertion sort work better when the array is almost sorted.

II. Insertion Sort will asymptotically work better when we use binary search instead of linear search.

III. Insertion sort best case is O(n²).

IV. Between insertion sort and Selection sort, Selection sort is preferred when swap is costly instead of insertion sort.

Given below are 4 functions, labelled I, II, III and IV.

I. 999999n

II. 0.99999n logn

III. 1.000001ⁿ

IV. n²

The increasing order of the above functions in terms of their asymptotic complexity is

Consider the following statements:

S₁: = n²⁰¹⁹ = O(n²⁰²⁰)

S₂: = O(n²⁰¹⁹) = O(n²⁰²⁰)

Which of the above statements is/are correct?

In Quicksort, which of the following is true?

i) Ideal for sorted array

ii) Works best when input is not almost sorted.

iii) worst case is O(n²)

iv) Better than insertion sort for every type of input.

Consider the following recurrence relation :

Which of the following best describes T(n) ?

Consider following functions:

f(n) = (log n)^n-1

g(n) = 2ⁿ

h(n) = eⁿ/n

Which of the following is true?

Consider an array containing ‘n’ elements. The elements present in an array are in arithmetic progression, but one element is missing in that order. What is the time complexity to find the position of the missing element using divide and conquer?

Given f(n) = θ(n), g(n) = Ω(n), h(n) = O(n). Then f(n) + [g(n) ⋅ h(n)] = ?

In the above algorithm, if input data items are already in sorted order then what is the Time complexity?

Consider the following function:

What is the worst case running time of the function f for any positive value of n ?