4 ms·

I have to disagree with you here. Let me put it this way: There are theoretical limits to the upper bound of problem size. The number of bits storable in the (

I have to disagree with you here. Let me put it this way: There are theoretical limits to the upper bound of problem size. The number of bits storable in the (observable) universe is only, what, about 10^120? [1] log32(10^120) is only around 80. So if you have a constant-time algorithm that runs around 80x slower than a logrithmic algorithm for small cases, the constant-time algorithm will never be faster. Period. And I've seem constant-time algorithms that take >80x the speed of theoretically asymptotically slower algorithms. I mean: a single cache miss can cause that level of slowdown. Or, to put it another way, log32(n) <= 80 for all achievable n. So, realistically, you might as well consider it effectively O(80), i.e. O(1). You have something similar, albeit more extreme, for inverse Ackermann time. [1] http://physics.aps.org/story/v9/st27 http://physics.aps.org/story/v9/st27

tolmasky 12y ago
Doesn't it matter in the way functions compose however? Definitely not my area of expertise, but similar to the classic N^2 iteration trap (for(i=0;i<strlen(str);++i) ...) you could see something like that happening by multiplying log operations together. For example, if for each item in a this vector, I have 2 nested inner loops where I act as if the operation is O(1), I start feeling like it should perform O(N), in reality though, its performing O(N * log32^2 N). If N is 1,000,000 (not an unreasonable amount by any means), we're now talking 1.5 * 10^7 operations vs 1 * 10^6 that I expect. Perhaps arguably not too unreasonable a slowdown, but its certainly affecting the way my application scales in a way that wasn't immediately intuitive when I initially wrote the code. Again, not sure if this is an practical worry, but curious if these seemingly small differences can magnify as they bubble up through composition.
- ajuc 12y ago
  If for all realistically possible n your O(log n) function is faster than O(1) function, then calling your function K times will still be faster than calling that O(1) function K times.
malisper 12y ago
> There are theoretical limits to the upper bound of problem size. Big O is defined as what happens as the size of the input approaches infinity. You cannot take a O(log n) algorithm and say it is effectively O(1), that is not what big O means. If anything, you are arguing for why big O notation is a bad measure for the efficiency of an algorithm, not why you can call a O(log n) algorithm O(1).
wtetzner 12y ago
From a quick look at the Clojure code, it looks like elements are indexed by ints. log_32(2 ^ 31) = 6.2.
ScottBurson 12y ago
That argument applies to any O(log n) algorithm. The base of the logarithm doesn't matter.
- TheLoneWolfling 12y ago
  Well, yes and no. Yes, in that the argument applies. No, in that the size is larger. It's more reasonable to say one algorithm is 80x faster than another of the same complexity than to say one algorithm is 530x faster than another of the same complexity.
- lomnakkus 12y ago
  Constants matter. To "overcome" O(log_a n) you need a constant of n^a for any given n. That's quite a lot in practice... although it's matematically trivial.
millstone 12y ago
With a mutable vector, the fast path for appending an object is to increment the count and store a value at the end. That's two stores. With a persistent vector, the fast path for appending an object is to allocate memory, copy the old structure into the new one (incurring several write barriers), increment the count, store the new object at the end, and then (eventually) deallocate the old structure. Is it that hard to imagine that the persistent vector fast path will be 80x slower than the mutable vector fast path? As you say, a single cache miss can be responsible for that slowdown, and a cache miss is likely with the freshly allocated memory. So then, by your argument, we ought to characterize the "constant time" persistent vector operation as logarithmic, since it's 80x slower.

tolmasky 12y ago

Doesn't it matter in the way functions compose however? Definitely not my area of expertise, but similar to the classic N^2 iteration trap (for(i=0;i<strlen(str);++i) ...) you could see something like that happening by multiplying log operations together. For example, if for each item in a this vector, I have 2 nested inner loops where I act as if the operation is O(1), I start feeling like it should perform O(N), in reality though, its performing O(N * log32^2 N). If N is 1,000,000 (not an unreasonable amount by any means), we're now talking 1.5 * 10^7 operations vs 1 * 10^6 that I expect. Perhaps arguably not too unreasonable a slowdown, but its certainly affecting the way my application scales in a way that wasn't immediately intuitive when I initially wrote the code. Again, not sure if this is an practical worry, but curious if these seemingly small differences can magnify as they bubble up through composition.

ajuc 12y ago
If for all realistically possible n your O(log n) function is faster than O(1) function, then calling your function K times will still be faster than calling that O(1) function K times.

malisper 12y ago

> There are theoretical limits to the upper bound of problem size. Big O is defined as what happens as the size of the input approaches infinity. You cannot take a O(log n) algorithm and say it is effectively O(1), that is not what big O means. If anything, you are arguing for why big O notation is a bad measure for the efficiency of an algorithm, not why you can call a O(log n) algorithm O(1).

wtetzner 12y ago

From a quick look at the Clojure code, it looks like elements are indexed by ints. log_32(2 ^ 31) = 6.2.

ScottBurson 12y ago

That argument applies to any O(log n) algorithm. The base of the logarithm doesn't matter.

TheLoneWolfling 12y ago
Well, yes and no. Yes, in that the argument applies. No, in that the size is larger. It's more reasonable to say one algorithm is 80x faster than another of the same complexity than to say one algorithm is 530x faster than another of the same complexity.
lomnakkus 12y ago
Constants matter. To "overcome" O(log_a n) you need a constant of n^a for any given n. That's quite a lot in practice... although it's matematically trivial.

millstone 12y ago

With a mutable vector, the fast path for appending an object is to increment the count and store a value at the end. That's two stores. With a persistent vector, the fast path for appending an object is to allocate memory, copy the old structure into the new one (incurring several write barriers), increment the count, store the new object at the end, and then (eventually) deallocate the old structure. Is it that hard to imagine that the persistent vector fast path will be 80x slower than the mutable vector fast path? As you say, a single cache miss can be responsible for that slowdown, and a cache miss is likely with the freshly allocated memory. So then, by your argument, we ought to characterize the "constant time" persistent vector operation as logarithmic, since it's 80x slower.