2 ms·
Glad I'm not the only one who cringed at that. Another thing to consider when using phrases like "O(logn)" is that the numbers grow exponentially with n (meani
by klipt 17y ago
Glad I'm not the only one who cringed at that.
Another thing to consider when using phrases like "O(logn)" is that the numbers grow exponentially with n (meaning their lengths grow linearly). Many CS students are trained to think of addition, multiplication etc. as "constant time" operations but that's not true for bignums!
BTW, I assume they meant difference equations.
- jules 17y agoGood point. Can you work out the asymptotics of the binary search algoritm, assuming multiplication is O(f(n))?