# 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? – Tom van der Zanden Jul 25 '16 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. – GreatDuke Jul 25 '16 at 12:26