# Finding integer square root for large integers [find asymptotic time complexity]

So I found this tasks in one book I am practicing from where it says: "Find a divide-and-conquer algorithm for finding square roots for large integers and along this, find its asymptotic time complexity". Results can be in integer range. I am not sure which algorithm should I use, but I started with recursive method where I count the medium between two borders and go on until i find the perfect score, or if begin border becomes greater than the end one. What I have problem here is how to measure complexity for this problem and I am not even sure does this method count as divide-and-conquer?

• That definitely sounds like divide and conquer. With regards to the analysis, are there any techniques you know for analyzing (recursive) algorithms? Are you familiar with the Master Theorem? Jul 25, 2016 at 12:14
• Yes, I am familiar with the Master Theorem. I know how to implement it for small integers, but for large ones I'm not quite sure. Jul 25, 2016 at 12:26