Computer Sciences > Gate 2022 > Complexity
Consider the problem of reversing a singly linked list. To take an example, given the linked list below,

Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in O(1) space?

A
The best algorithm for the problem takes θ(n) time in the worst case.
B
The best algorithm for the problem takes θ( nlog n) time in the worst case.
C
The best algorithm for the problem takes θ(n2) time in the worst case.
D
It is not possible to reverse a singly linked list in O(1) space.

Correct : a

Similar Questions

Consider a complete binary tree where the left and the right subtrees of the root are max-heaps. The lower bound for the number of operations to convert the tre...
#50 MCQ
Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting n ( ≥ 2) numbers? In the recurr...
#81 MCQ
Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are T...
#109 MCQ

Related Topics

No tags found

Unique Visitor Count

Total Unique Visitors

Loading......

Question Options

Contributed by: