To determine the running time in the word-RAM model, we have to account for the cost of calling \(\mathtt{findIt(a,x)}\) for each node we access, so the running time of \(\mathtt{find(x)}\) in the wor...To determine the running time in the word-RAM model, we have to account for the cost of calling \(\mathtt{findIt(a,x)}\) for each node we access, so the running time of \(\mathtt{find(x)}\) in the word-RAM model is The executive summary of the \(\mathtt{add(x)}\) method is that it walks from the root to a leaf searching for \(\mathtt{x}\), adds \(\mathtt{x}\) to this leaf, and then walks back up to the root, splitting any overfull nodes it encounters along the way.
