[twawaaay]

Please, read the question.

It stipulates that elements are selected at random.

You select k integers at random.

Some of them might be inserted faster into linked list, but when you average it over k integers you will still be slower because inserting into array will be faster, on average.

Just think what happens if the integer is inserted at the END of the list (same probability...) You need to slowly iterate over entire linked list. While you quickly land at the result with a binary search on an array and then pay almost no cost inserting it there.

If you think about it, ON AVERAGE, you have to search through half of the list (if you are linked list) or move half of the array (if you are an array).

[jwilk]

The parts of simiones's message you quoted are not about the average case. They are about the corner case when an item would be added the beginning, meaning the linked list has the biggest advantage.

[twawaaay]

You don't get to change the rules of the game while the game is being played.

The original problem, as stated by me, was:

"You are generating k random 64 bit integers. Each time you generate the integer, you have to insert it in a sorted collection.

(...)

The question: in your estimation, both algorithms being implemented optimally, what magnitude k needs to be for the linked list to start being more efficient than array list."

The cost is not evaluated for any individual insertion, only for the total cost of inserting k integers.

For some of the integers the cost of inserting to linked list will be higher, and for some the cost of inserting to array will be higher. It does not matter. We do not care. We just care about what is the cost of inserting k integers thus randomly generated a) into sorted linked list and b) into sorted array list.