Problem Detail: Here’s the code for the algorithm:
Foo(n) lcm = 1 for i = 2 to n lcm = lcm*i/Euclid(lcm,i) return lcm
The running time of Euclid$(a, b)$ is given as $O(log(min(a, b)))$ So the running time of the for loop will be $O(n)$, so would this be the final running time? or do I have to take the $O(log(min(a, b)))$ into account as well?
Asked By : cjang5
Answered By : Yuval Filmus
The running time for the loop will be $$ Oleft(sum_{i=2}^n (1+log min(operatorname{lcm}(1,2,ldots,i-1),i))right). $$ The $1$ takes care of the arithmetic operations beyond GCD, and the other term is the running time of GCD, as given to your. The arguments to GCD are lcm and i. The value of lcm at iteration $i$ is $mathrm{lcm}(1,2,ldots,i-1)$, explaining the complete formula. We can upper bound this sum by $$ Oleft(sum_{i=2}^n (1 + log i)right) leq Oleft(sum_{i=2}^n (1 + log n)right) = O(nlog n). $$
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/23835 Ask a Question Download Related Notes/Documents
