4 ms·
And you would iterate through that sequence? That's exponential time in the bit length of the input...
by atq2119 3y ago
And you would iterate through that sequence? That's exponential time in the bit length of the input...
- sublinear 3y agoIt's sqrt(n) - 1 additions for the n you're trying to get the integer square root of. Memoization would make it constant time for any lesser n than the greatest n you've done this for. For greater n it's sqrt(new_big_n - prev_big_n) - 1 more additions to memoize. You're right this isn't practical, but fun to think about. Good refresher for those out of school for a while.
- klyrs 3y agoSubtle detail of complexity analysis: the input is of length log(n), so taking n^k steps for any positive number k is exponential time.