3 ms·
It's not O(n): both 'nth' and 'butnth' are themselves O(n), and get called 'n' times. I'm fairly certain you'll end up with O(n^2) unless you introduce mutation
by crux_ 17y ago
It's not O(n): both 'nth' and 'butnth' are themselves O(n), and get called 'n' times. I'm fairly certain you'll end up with O(n^2) unless you introduce mutation. I'm also fairly certain there is no purely functional O(n) algorithm. ;)
- astine 17y agoYou're right of course; I'm not looking very deeply. I'm also fairly certain there is no purely functional O(n) algorithm. (defun nth (index list) (if (zerop index) (first index) (nth (1- index) (rest list))))
- crux_ 17y agoI meant for perfect shuffling, not 'nth'. :) This is for you, since I've already had three today & the brainos in your nth implementation are a strong indication for its prescription: http://www.espressoguide.net/resources/images/articles/A002Image01.jpg http://www.espressoguide.net/resources/images/articles/A002I... Cheers!