For each of the following modifications of the sorted linked list algorithms, explain why the respective algorithm is still linear iz able, or give a counterexample showing it is not. a. In the...

For each of the following modifications of the sorted linked list algorithms, explain why the respective algorithm is still linear iz able, or give a counterexample showing it is not.

a. In the optimistic algorithm, the contains()method locks two nodes before deciding whether a key is present. Suppose, instead, it locks no nodes, returning true if it observes the value, and false other wise.

b. In the lazy algorithm, the contains()method executes without inspecting the locks, but it inspects the mark bit; it returns false if a node is marked for removal. Suppose, instead, the contains()does not inspect the mark bit of the nodes, and returns true even for nodes that may be marked.