2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ What do you think? What have you tried? We expect you to make a serious effort before asking. You'll need to do your own exercises; there is a reason why they are assigned to you -- the way you learn is by doing the exercise yourself, not by asking someone else to solve it for you. $\endgroup$ – D.W. Apr 16 '14 at 1:29
  • 1
    $\begingroup$ @D.W. What the OP has thought and tried is included in the question. It's short but it's a short exercise. They have a specific question about their attempt, which is what we generally ask for. I don't think this falls under "Unclear what you're asking." $\endgroup$ – David Richerby Apr 16 '14 at 6:30
  • 1
    $\begingroup$ I think it's more likely that we can help the poster if they show their reasoning. Is "So it will be O(n)" a guess, or how'd they get to that answer? Showing the details of the calculation or reasoning they used to get O(n) would make this question more readily answerable. $\endgroup$ – D.W. Apr 16 '14 at 6:49
  • 1
    $\begingroup$ Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – FrankW Apr 16 '14 at 7:28
  • $\begingroup$ Note also our reference questions on this. $\endgroup$ – Raphael Apr 16 '14 at 8:18
3
$\begingroup$

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). $$

$\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.