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!