Great and very detailed article!
Fragment of a discussion from Talk:Binary Search PIF
Jump to navigation
Jump to search
Well, that’s only true for large enough n... And for small n, such as our cases, constant factor is dominant.
Btw, memory access is WAAAY expensive than basic calculations, so the gain for optimized memory access, for small n, often outperforms paper algorithms that don’t use contiguous memory in order.
