3 ms·
I always thought the Russian peasants algorithm was faster than this at O(log n). Can someone explain what I've misunderstood?
by fny 7y ago
I always thought the Russian peasants algorithm was faster than this at O(log n). Can someone explain what I've misunderstood?
- naniwaduni 7y agoConventionally n is the length of the input, which is generally logarithmic in the numerical value of the input for algorithms dealing in integers. Moreover, analyzing Russian peasant multiplication as O(log N) implies treating addition as constant-time, which it certainly isn't. (This is intuitively clear if we try applying the algorithm with slightly large integers!)