2 ms·
You are assuming division itself is an O(1) operation. However, it also scales with the size of the number. So more correct would be to say that this naive meth
by gsliepen 11mo ago
You are assuming division itself is an O(1) operation. However, it also scales with the size of the number. So more correct would be to say that this naive method is O(sqrt(N) log(N) log(log(N))).
- xpe 11mo agoI was both hoping and fearing that someone would correct my simplification. (That is more nested logs than I would’ve guessed however.)