[Solved]: Big O running time for this algorithm?

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 $$ O\left(\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 $$ O\left(\sum_{i=2}^n (1 + \log i)\right) \leq O\left(\sum_{i=2}^n (1 + \log n)\right) = O(n\log n). $$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/23835

 Ask a Question

 Download Related Notes/Documents