Question

The worst case running time of a linear search on the self organizing list is ____

(a) O(1)

(b) O(logn)

(c) O(n)

(d) O(n^2)

This key question is from Types of Lists in section Types of Lists of Data Structures & Algorithms I

This question was addressed to me during an interview.

Answer 1

The correct answer is (c) O(n)

The best I can explain: Worst case occurs when the element is located at the very end of list. So n comparisons must be made to the locate element. So the worst case running time of linear search on self organizing list is O(n).