Give the complexity of each operation and explain it: removing an element from a sorted array, checking for a key in a hash map, removing the smallest element of a min-heap, and finding an element in a sorted linked list.