0
$\begingroup$

This question is specifically related to

https://stackoverflow.com/questions/3980416/time-complexity-of-euclids-algorithm

The $gcd(x,y)$ is solved in $O(T(n) log n)$, where $n$ is the number of bits of $x,y$, and $T(n)$ is the time to multiply two $n$ bit numbers, as described in

How is the Time Complexity of a Function Problem different than its corresponding Decision Problem?

so when it reads "if you're dealing with big integers, you must account for the fact that the modulus operations within each iteration don't have a constant cost. Roughly speaking, the total asymptotic runtime is going to be $n^2$ times a polylogarithmic factor. Something like n^2 lg(n) 2^O(log*n). "

Isn't this the same thing as stating "the fastest $gcd(x,y)$ is solved in n^2 lg(n) 2^O(log* n)"? If so, then

How could a total asymptotic runtime exceed the upper bound of an algorithm's runtime?

If the $gcd(x,y)$ is solved in $O(T(n) log n)$, shouldn't this be true no matter how large $n$ is?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ I'm having a hard time understanding what you are asking. I suspect there is a faulty premise somewhere, but I'm having a hard time telling exactly what it is. For the first question, why would it be the same thing as stating "the fastest..."? No, I don't see any reason it should be the same, but you don't tell us your reasoning so it's hard to know where you've gone wrong. I don't understand what you mean by a "a total asymptotic runtime exceed.." or how that is connected to the rest of the post. The final question indicates you should study the definition of big-O notation further. $\endgroup$ – D.W.♦ Jan 30 '18 at 6:57
  • $\begingroup$ @D.W., at the first link above, Craig writes "Of course, if you're dealing with big integers, you must account for the fact that the modulus operations within each iteration don't have a constant cost. Roughly speaking, the total asymptotic runtime is going to be n^2 times a polylogarithmic factor. Something like n^2 lg(n) 2^O(log* n). The polylogarithmic factor can be avoided by instead using a binary gcd." It is this wording I do not understand myself. I assume he knows what he is talking about, so I am first asking others what that is. $\endgroup$ – Jeff Jan 30 '18 at 15:12
1
$\begingroup$

It is just that the first expression doesn't count the cost of the divisions, that is factored in later.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you! And thank God for no nonsense. :) $\endgroup$ – Jeff Feb 28 '20 at 16:12
2
$\begingroup$

Based on your comments, I recommend go back to basics and first understand running time, bit-complexity, and the running time for multiplication well. Focus on that before you try to tackle any of the topics in this post, or you're going to get confused.

Here is a suggested syllabus:

  1. First, study big-O notation. Understand what it means. Work through the definitions. This is well covered in standard algorithms textbooks, so work through that material patiently. See also, e.g., How does one know which notation of time complexity analysis to use?, How to come up with the runtime of algorithms?. Try to understand why your "shouldn't this be true no matter how large n is?" question is meaningless (hint: big-O notation relates two functions, not two numbers).

  2. Understand bit complexity as a measure of running time for algorithms that work with large numbers. See, e.g., Precise runtime of the algorithm to find number of digits in an integer, Relationship between an integer N and the number of bits n required to represent the integer

  3. Understanding the bit complexity of addition. This will be a good test whether you understand bit complexity. See, e.g., Time complexity of addition.

  4. Understand the bit complexity of multiplication. Understand why it is an open problem how fast we can multiply two integers. See, e.g., Complexity of multiplication, https://en.wikipedia.org/wiki/Multiplication_algorithm, Complexity of a recursive bignum multiplication algorithm, What is the fastest algorithm for multiplication of two n-digit numbers?.

  5. Understand the bit complexity of division and modular reduction. See, e.g., Complexity of Integer Division, Complexity of taking mod.

If there is any of these steps you are unclear on, ask a question about that specific aspect until you understand it well. Then, go back and study the material on gcd's. This background material will probably help you make it further through that material.

Remember that just because there is an algorithm to solve some problem in time $O(f(n))$, doesn't necessarily mean that that is the fastest algorithm to solve that problem. It doesn't mean that is the fastest that the problem can be solved. For instance, bubblesort can be used to sort numbers; it has a $O(n^2)$ running time. That doesn't mean that $O(n^2)$ is the "fastest that numbers can be sorted".

Improve this answer
$\endgroup$
2
  • $\begingroup$ When one asks, "what does...?" or "how does one...?", a reasonable answer is not..."research more". I cannot stress my down-vote enough on this response. I would like more clarification on the question asked, rather than "answers" beginning with "Understand". EXPLAIN, then someone might understand. THIS HERE is the forum to make the answer clear...not another text where the question is forwarded. If the answer can be made clear here, then give it a try or let someone else. $\endgroup$ – Jeff Jan 31 '18 at 4:12
  • $\begingroup$ @Jeff, I'm sorry that this wasn't helpful to you. As I indicated in my comment, I'm having trouble understanding what you are asking, and I'm not sure exactly what to explain. If this wasn't helpful, I understand. I hope someone else will be able to provide a more useful answer. $\endgroup$ – D.W.♦ Jan 31 '18 at 4:20

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.