[Chattered]

I'm not sure on the specifics here, but I'd have thought that subtraction would be O(n). To perform n - m on a simple register machine with only increment, you just count from m up to n (and count from 0 up to n, outputting 0 if you reach n, since subtraction is partial).

EDIT: It seems they are going for a naive implementation where subtract just repeatedly calls decrement, so yes, that's going to be O(m*n).

[auggierose]

It depends on what the n means in O(n). If n means anything other than "the number of digits of x" (i.e., n = log(x)), then this is absurdly slow.

[Chattered]

The n is just n: it's the number you are subtracting from. Of course, it's impractically slow, but I believe it's just example code in a opening tutorial for the Nock language.

[yebyen]

You are both right. Nock is not meant to be fast.

There are only 10 operators in Nock, and when you get to the last one, you see there's a space for a "hint" to the compiler. This is how Nock becomes fast in Hoon. You start with an extremely slow, naive implementation, and then you write something called a "jet" which is proven (I think usually a weak proof is considered sufficient, like by fuzzing) to be semantically equivalent to the nock that it replaces. Then you do your best to make sure you use that exact expression anywhere you mean that, and don't reinvent it again later.

Jets are currently written in C, since the vere platform is written in C. Learning how they work and how to write them is on my bucket list.