You are viewing a single comment's thread. Return to all comments →
Good Point! I wasn't aware that we used Newton's method for that. However, I don't believe this changes the algorithmic complexity here. When you say Newtons method has complexity O(log(n)), I believe that n here refers to the precision of the number not the size of the input. Thus if you fix the precision (I don't see you wouldn't) then calculation is roughly constant from our perspective. See; http://stackoverflow.com/questions/5005753/what-is-newton-raphson-square-methods-time-complexity/5005879#5005879 and http://en.citizendium.org/wiki/Newton%27s_method#Computational_complexity
Seems like cookies are disabled on this browser, please enable them to open this website
Sherlock and Squares
You are viewing a single comment's thread. Return to all comments →
Good Point! I wasn't aware that we used Newton's method for that. However, I don't believe this changes the algorithmic complexity here. When you say Newtons method has complexity O(log(n)), I believe that n here refers to the precision of the number not the size of the input. Thus if you fix the precision (I don't see you wouldn't) then calculation is roughly constant from our perspective. See; http://stackoverflow.com/questions/5005753/what-is-newton-raphson-square-methods-time-complexity/5005879#5005879 and http://en.citizendium.org/wiki/Newton%27s_method#Computational_complexity