Re:Two problems I had to solve in my Oxford interview (2013)
by Strilanc on Monday May 11, 2015 @08:23PM
(#9528762)
A common implicit assumption in complexity analysis is that machine words can hold O(lg n) bits, and that those words can be operated on in constant time.
Lots and lots of algorithms gain an extra lg(n) factor if you drop that assumption.
Lots and lots of algorithms gain an extra lg(n) factor if you drop that assumption.
e.g. http://blog.computationalcomplexity.org/2009/05/shaving-logs...