Commitcbb7b39

authored

Update euclid-algorithm.md

1 parent723dc71 commitcbb7b39Copy full SHA for cbb7b39

File tree

-1

lines changed

-1

lines changed

Lines changed: 1 addition & 1 deletion

Original file line number	Diff line number	Diff line change
`@@ -70,7 +70,7 @@ Moreover, it is possible to show that the upper bound of this theorem is optimal`
`70`	`70`
`71`	`71`	`Given that Fibonacci numbers grow exponentially, we get that the Euclidean algorithm works in $O(\log \min(a, b))$.`
`72`	`72`
`73`		`-Another way to estimate the complexity is to notice that $a \bmod b$ for the case $a \geq b$ is at least $2$ times smaller than $a$, so the larger number is reduced at least in half on each iteration of the algorithm.`
	`73`	+Another way to estimate the complexity is to notice that $a \bmod b$ for the case $a \geq b$ is at least $2$ times smaller than $a$, so the larger number is reduced at least in half on each iteration of the algorithm. Applying this reasoning to the case when we compute the GCD of the set of numbers $a_1,\dots,a_n \leq C$, this also allows us to estimate the total runtime as $O(n + \log C)$, rather than $O(n \log C)$, since every non-trivial iteration of the algorithm reduces the current GCD candidate by at least a factor of $2$.
`74`	`74`
`75`	`75`	`## Least common multiple`
`76`	`76`

Comments

(0)