According to Devel::Peek, it's an array rather than a linked list. That doesn't change the complexity, though.
To delete weak ref #X:
O(X) to locate + O(N-X) to delete
= O(N) total
Best, average and worse case to delete one weak ref of N is O(N).
To delete all N weak refs:
O(N) + O(N-1) + O(N-2) + ... + O(1)
= O(N**2)
Best, average and worse case to delete all N weak refs is O(N**2).
A hash, on the other hand, would scale much better.
Best, average and worse case to delete one weak ref of N is O(1).
Best, average and worse case to delete all N weak refs is O(N).
Update: Added analysis for hash.
|