3 ms·
You say addition is O(n^2), but I think you can write an O(n) addition with only increment, recursion, and equality testing. In Python syntax: def add(a, b)
by tlb 13y ago
You say addition is O(n^2), but I think you can write an O(n) addition with only increment, recursion, and equality testing.
In Python syntax:
def add(a, b):
return add_r(a, b, 0)
def add_r(a, b, c):
if b == c:
return a
else:
return add_r(a, b, c+1) +1
- jcburnham 13y agoYeah... just one of the many many things we haven't gotten around to fixing. Since it doesn't really matter for a jet-propelled function. https://github.com/urbit/urbit/issues/11 https://github.com/urbit/urbit/issues/11
- urbit 13y agoYeah, it's true, the one in our kernel is O(n^2) though. Why? Because we're lame. But it hardly matters, as you'll never get anywhere with either O(n) or O(n^2) addition...
- deleted 13y ago[deleted]
- betenoire 13y agoIt's python, so it can't handle it either way, but by moving the final "+1" into the function call, it becomes tail-recursive. return add_r(a+1, b, c+1)