Diferente pentru blog/square-root-trick intre reviziile #102 si #101
Nu exista diferente intre titluri.
Diferente intre continut:
return s ==
Each query takeson average$k/2+ n/k + k/2= k + n/k$ time.This is minimized for $k = sqrt(n)$.Sowe get a $O(sqrt(n))$ time complexity query.
Each query takes less than $k + n/k + k = 2k + n/k$ time. For $k = sqrt(n)$ we get a $O(sqrt(n))$ time complexity query.
This trick also works for other associative operations, like: min, gcd, product etc.
Diferente intre securitate:
protected
public