Computer Sciences > Gate 2022 > Complexity

Contributed by: Dr. Sarah Chen

Report Correct Copyright Claim

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 θ(n²) time in the worst case.

D

It is not possible to reverse a singly linked list in O(1) space.

Check Answer

Explanation

Correct : a

Similar Questions

What is the worst-case time complexity of insertion in an AVL tree?

Question #23 Medium

Which operations on a binary search tree have O(h) complexity?

Question #31 Easy

Compare search complexities of sorted array vs balanced BST.

Question #47 Hard

Related Topics

Data Structures Binary Search Tree Time Complexity Algorithm Analysis Tree Algorithms Computer Science