Consider the binary search problem on a sorted array containing $n$ integers on16 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 tocalculate a midpoint. The first midpoint is $[n/2]$. The next midpoint couldbe $[n/2]+[n/4]$. If the searched number is placed in the second half of thearray, 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 eachmidpoint calculation requires $O(\log(n))$. I obtain a more precise complexityof $O(\log(n)^2)$. Where is the error?The same problem could appear on countless algorithms that use arrays ormatrices. Take the most well-known dynamic programming algorithm for theknapsack problem. Everybody agrees it takes $O(nW)$ time (e.g., thewikipedia 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 ofweights/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 neededit, 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. 
Where/how did a $\log(n)$ factor disappear from well-known algorithms?
complexity theory;polynomial time