Storage cost: O(V+E) (V list pointers, total of 2·E list elements)
- the larger of V,E determines the complexity
Cost of operations:
- initialisation: O(V) (initialise V lists)
- insert edge: O(1) (insert one vertex into list)
- if you don't check for duplicates
- find/delete edge: O(V) (need to find vertex in list)
If vertex lists are sorted
- insert requires search of list ⇒ O(V)
- delete always requires a search, regardless of list order
|