Hacker News new | comments | show | ask | jobs | submit login

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
      return add_r(a, b, c+1) +1

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

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.


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 | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact