User talk:Retroburrowers: Difference between revisions

for i in range(0, (int(math.sqrt(kn)) - 3) // 2 + 1):

: This difference in the amount of operations as in the amount of work done gets even larger as the range goes up; if you want to play with it, the code is posted on [https://wandbox.org/permlink/IXqqq4DKriRNJApbI5PmD0YsAW0ndm6q an on-line IDE here]. The reason this is true is that the SoE has about O(n log log n) asymptotic complexity which increases quite slowly with range, where as the SoS has o(n^(3/2)n log n) complexity, which increases quite quickly with range. This can be seen from the above implementation as ''i'' ranges up the the square root of (half of) the range, where the ''j'' variable ranges from a little above ''i'' for something approaching (half of) the range, so the product is O(n^(3/2)) but the span of the culling increases with increase base number so as to reduce the term to about ''log n'', with the constant extra factor of about a quarter meaningless for showing complexity with increasing range (Big-O).