3 ms·
It's a constant number of lookups, and all good Computer Scientists know that it is therefore an O(1) algorithm. It is hard to imagine better efficiency than O
by xnorswap 11mo ago
It's a constant number of lookups, and all good Computer Scientists know that it is therefore an O(1) algorithm.
It is hard to imagine better efficiency than O(1)!
Indeed we could improve it further by performing all evaluations even when we find the answer earlier, ensuring it is a true Constant Time algorithm, safe for use in cryptography.
- nixpulvis 11mo ago> This is time efficient* but rather wasteful of space. You're saying that the blog's solution is time efficient. Which it is not. Your solution may be O(1) but it is also not efficient. As I'm sure you are aware. I can tell you a practical solution which is also O(1) and takes up maybe 2 or 3 instructions of program code and no extra memory at all. `x & 1` or `x % 2 != 0` This blog post was taking a joke and running with it. And your comment is in that spirit as well, I just wanted to point out that it's by no means time efficient when we have 2s or 1s complement numbers which make this algorithm trivial.
- icambron 11mo agoYou need to read their entire comment as a joke.
- nixpulvis 11mo agoI guess I should have been more clear that I was just pointing out the obvious in case some confused reader missed the joke. lol
- henrikschroder 11mo ago> I just wanted to point out that We already know. Everybody knows. That's the joke. There's no need to point out anything.