Follow Us :

Data Structures and Algorithms - Performance Analysis of Algorithms and Recurrences

Avatto > > UGC NET COMPUTER SCIENCE > > PRACTICE QUESTIONS > > Data Structures and Algorithms > > 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

  • Option : D
  • Explanation :
    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).
Cancel reply
Cancel reply

72. Consider the equality and the following choices for X
I. θ(n4)
II. θ(n5)
III. O(n5)
IV. Ω(n3)
The equality above remains correct if X is replace by

  • Option : C
  • Explanation :
    I or III or IV but not II
    as
    this can be represent by Θ(n4, O(n5), Ω(n3) but not Θ(n5)
Cancel reply
Cancel reply

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))

  • Option : D
  • Explanation :
    As – 1 ≤ sin x ≤ 1, neither of them is true
Cancel reply
Cancel reply

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

  • Option : A
  • Explanation :
    The worst case recurrence reaction for flow chart is
    T(n) = 5 T(n/2)+ 1
    Apply master’s method
    n log25 ⇒ n2.32 > 1
    T(n) = O(n2.32)
    So, α = 2.32
Cancel reply
Cancel reply

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?

  • Option : C
  • Explanation :
    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(N2) All operations put together than worst time is O(N2)
Cancel reply
Cancel reply
Related Quiz.
Performance Analysis of Algorithms and Recurrences