4 ms·
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
by 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 agoIf 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.