[prev] 27 [next]

Cost Analysis

Storage cost: O(E)

Cost of operations:

  • initialisation: O(1)
  • insert edge: O(1)   (assuming edge array has space)
  • find/delete edge: O(E)   (need to find edge in edge array)
If array is full on insert
  • allocate space for a bigger array, copy edges across ⇒ O(E)
If we maintain edges in order
  • use binary search to insert/find edge ⇒ O(log E)
    (requires binary search tree of edges → week 4)