The true cost of linked lists

Re:The true cost of linked lists by glitchc on Monday June 06, 2022 @09:51AM (#31640460)

This is incorrect. Putting a finite bound on n does not reduce n to 1. n is always meant to be a finite arbitrarily large value. n=INT_MAX qualifies as arbitrarily large, especially on a 64-bit system.

[ Parent | on HN ]

Re:The true cost of linked lists by Sohcahtoa82 on Monday June 06, 2022 @05:30PM (#31646550)

Big-O notation says nothing about the overall absolute size. All that matters is how the amount of work scales with the input value.

If an algorithm will always take 1 billion years to complete regardless of the input, then it's still O(1).

[ Parent | on HN ]

Re:The true cost of linked lists by carnitine on Monday June 06, 2022 @10:37AM (#31641069)

O(x) = O(1) if x is some finite constant.

[ Parent | on HN ]

Re:The true cost of linked lists by 8note on Monday June 06, 2022 @06:10PM (#31647041)

Consider n=INT_MAX*2 or INT_MAX^2 though.

The behaviour does flatline as n approaches infinity

[ Parent | on HN ]

Re:The true cost of linked lists by PhineasRex on Monday June 06, 2022 @12:30PM (#31642563)

There is no bound on n, it always searches to INT_MAX regardless of n.

[ Parent | on HN ]