It says in the relevant presentation that the naive approach to GCD is O(2^n), why is that? Doesn't it iterate exactly min(k,l) times, hence O(n)?
Date: 05 Feb 2015 09:31
Number of posts: 4
RSS: New posts
By what definition of complexity? Usually in class and in general we counted arithmatic calculations and conditionals as O(1), taking note only of the number of iterations. If the code does iterate only min(k,l) times (k and l being integers), how is it considered exponential complexity?
The number of operations is O(min(k,l)) (indeed, conditionals, arithmetic calc etc. are O(1))
As Michal said, O(min(k,l)) is O(2^n) where n is the number of bits.
As we said in class, a first step in complexity analysis is specifying complexity in terms of what is analyzed. In this case (as in many other cases related to numerical computations) we were interested in the complexity in terms of the number of bits -
if we have'nt specified this, then O(min(k,l)) would also be a valid answer.