Shouldn't the average search time for a linked list be O(N/2)?

Question

I keep seeing the search time for linked lists listed as O(N) but if you have 100 elements in a list aren't you on average only comparing against 50 of them before you've found a match?

So is O(N/2) being rounded to O(N) or am I just wrong in thinking it's N/2 on average for a linked list lookup?

Thanks!

Answer 1

The other answers make the main points required for the answer, but there's a detail I'd like to add: If it's not explicitly stated, complexity statements typically discuss the worst case behaviour, rather than the average, simply because analysing the worst case behaviour is frequently a lot easier than the average behaviour. So if I say, without any additional qualifications, search in a linked list is O(N), then I'm admittedly being sloppy, but I would be talking about the worst case of search in a linked list taking a number of steps linear in N.

Answer 2

The thing is, the order is really only talking about how the time increases as n increases.

So O(N) means that you have linear growth. If you double N then the time taken also doubles. N/2 and N both have the same growth behaviour so in terms of Order they are identical.

Functions like log(N), and N^2 on the other hand have non-linear growth, N^2 for example means that if you double N the time taken increases 4 times.

It is all about ratios. If something on average takes 1 minute for 1 item will it on average take 2 minutes or 4 minutes for 2 items? O(N) will be 2 minutes, O(N^2) will take 4 minutes. If the original took 1 second then O(N) will take 2 seconds, O(N^2) 4 seconds.

The algorithm that takes 1 minute and the algorithm that takes 1 second are both O(N)!