Consider the binary search problem on a sorted array containing $n$ integers on 16 bits. Everybody agrees that the binary search needs $O(\log(n))$ time, because it makes at worst $O(\log(n))$ steps. But: at each step it needs to calculate a midpoint. The first midpoint is $[n/2]$. The next midpoint could be $[n/2]+[n/4]$. If the searched number is placed in the second half of the array, the midpoint at each step is no less than $[n/2]$. Each calculation of a new midpoint involves at least a number with $O(\log(n))$ bits, hence each midpoint calculation requires $O(\log(n))$. I obtain a more precise complexity of $O(\log(n)^2)$. Where is the error?
The same problem could appear on countless algorithms that use arrays or matrices. Take the most well-known dynamic programming algorithm for the knapsack problem. Everybody agrees it takes $O(nW)$ time (e.g., the wikipedia article on the knapsack problem), where $n$ is the number of items and $W$ is the capacity. But at each step, it needs to compute a difference of weights/capacities, which should account for an additional factor of $O(\log(W))$. Where is the error?
Where/how does this $O(\log(n))$ complexity factor disappear? If we had needed it, it would have appeared in many algorithms.
ps. A very similar problem arises in the questions asked here and here, thanks Ariel, Raphael and ryan for pointing this out.