Question

What would be the asymptotic time complexity to find an element in the linked list?

(a) O(1)

(b) O(n)

(c) O(n^2)

(d) O(n^4)

This is a very interesting question from Singly Linked List Operations topic in chapter Abstract Data Types of Data Structures & Algorithms I

I got this question by my college director while I was bunking the class.

Answer 1

Correct answer is (b) O(n)

For explanation: If the required element is in the last position, we need to traverse the entire linked list. This will take O (n) time to search the element.