2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Tom van der Zanden Jul 25 '16 at 12:14
  • $\begingroup$ 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. $\endgroup$ – GreatDuke Jul 25 '16 at 12:26
2
$\begingroup$

Normally, you don't measure the complexity of a problem before designing an algorithm; instead, you measure the complexity of a particular algorithm. So, before you get to measuring complexity, the first step is to come up with a specific algorithm.

When you have a specific algorithm in mind, one technique that's useful for analyzing the running time of divide-and-conquer algorithms is to write down a recurrence relation characterizing its running time, and then solve the recurrence. You can often use the Master theorem to solve the recurrence.

To learn these techniques, see your favorite algorithms textbook, or read the following resources:

$\endgroup$
0
$\begingroup$

What you are describing is something related to binary search to find the square root but it does not look to me like divide and conquer, why?, you are choosing a half of the interval each time not merging the result of the recursive calls which is the "conquer" part. That said, there is a discussion about if binary search is divide and conquer or not here is a good discussion with links provided : https://stackoverflow.com/questions/8850447/why-is-binary-search-a-divide-and-conquer-algorithm

About the complexity: what you should do is to come up with a recurrence relation from the time your algorithm takes based on the steps In each case of the recursive calls, then you solve that equation usually with Master method (but is not always the case).

If you **really ** want a divide and conquer with the "merge" part I suggest you to see the square root as an exponent and decompose it in subproblems and solve it, hint: if you multiply two powers with the same base how do you merge the exponents?. Nevertheless, it would be slower than the binary search approach.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.