It'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.
Comments
It'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.
Subtle detail of complexity analysis: the input is of length log(n), so taking n^k steps for any positive number k is exponential time.