Data Structures and Algorithms MCQ - Performance Analysis of Algorithms and Recurrences

71 An unordered list contains n distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum is

Suppose a list contains n elements, consider first three element and find middle element which will be neither maximum nor minimum. Hence it is θ(1).

72 Consider the equality

and the following choices for X
I. θ(n⁴)
II. θ(n⁵)
III. O(n⁵)
IV. Ω(n³)
The equality above remains correct if X is replace by

I or III or IV but not II
as

this can be represent by Θ(n⁴, O(n⁵), Ω(n³) but not Θ(n⁵)

73 Let f(n) = n and g(n) = n^{(1 + sin n)}), where n is a positive integer. Which of the following statements is/are correct?
I. f(n) = O(g(n))
II. f(n) = Ω(g(n))

As – 1 ≤ sin x ≤ 1, neither of them is true

74 The given diagram shows the flow chart for a recursive function A(n). Assume that all statements, except for the recursive calls, have O(1) time complexity. If the worst case time complexity of this function is O(n^α), then the least possible value (accurate up to two decimal positions) of a is ________.
Flow chart for Recursive Function A(n)

Note: Numerical type question

The worst case recurrence reaction for flow chart is
T(n) = 5 T(n/2)+ 1
Apply master’s method
n ^log₂⁵ ⇒ n^2.32 > 1
T(n) = O(n^2.32)
So, α = 2.32

75 N items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be deleted. For a decrease-key operation, a pointer is provided to the record on which the operation is to be performed. An algorithm performs the following operations on the list in this order: Θ(N) delete, O(log N) insert, O(log N) find, and Θ(N) decrease-key. What is the time complexity of all these operations put together?

Delete operation require O(1) time total O(N) Delete so time is = O(n).
Insert require O(n) time in worst case total O (logn) insert so time is = O(Nlogn) to Search (logn) key time is = nlogn.
To perform decrease key we need O (n) time (because after decrease we need to arrange elements in sorted sequerce) so total O(N) decrease key So total time is O(N²) All operations put together than worst time is O(N²)