Regarding the Floyd-Warshall algorithm's O(n^2) storage

Question

Why is storage in the Floyd-Warshall algorithm? Wouldn't it be less than that if a linked-list was used as opposed to an N by N matrix?

Answer 1

The worst-case size of that linked list would still be O(n^2) (I think? I'm not entirely sure I understand how you propose to use it), but the lookup cost would be sufficiently expensive to change the asymptotic complexity of the overall algorithm (operations on linked lists do not have the same complexity as operations on matrices of known size).