Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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


Yeah... 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


Yeah, 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...


It'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)




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: