Time to find the largest element in a Linked list

Question

I have an ordered linked list. I want to know the time to find the max element in both cases:

• If I maintain a tail pointer to the end of the linked list, and
• If I do not do so.

Answer 1

For ordered linked list:

• O(1) if the list is ordered from max to min as the first one is already the max one.

• O(n) if the list is ordered from min to max, it will become O(1) if you further have the tail pointer. The reason is that the max element is the last one in the linked list. Thus you have to traverse to the tail (O(n)). On the other hand, this will be O(1) when you have the tail pointer, you just return what the tail pointer pointers to.

For un-ordered linked list:

• Always O(n) no matter you have the tail pointer or not. The reason is that, for an un-ordered lined list, you have to traverse (O(n)) each one to determine which one is the max. And it cannot help even with a tail pointer.