Time complexity of floor_sum
rsk0315 opened this issue · 3 comments
rsk0315 commented
The document says O(log(m+a)), but now (by #92) m+a may be negative or zero. I suggest O(log(a mod m)).
By the way, maybe, its complexity could be bounded by O(log(min(n, a mod m))). It might be wrong because I guessed just intuitively (and empirically). So I'm glad if anyone can analyze this.
rsk0315 commented
Oh. Obviously, a mod m may be zero. 😢
How about O(log((a mod m)+1))?
rsk0315 commented
O(log(1)) equals O(0), which is not suitable.
O(max(1, log((a mod m)+1))), O(log((a mod m)+2)), or something like that? 😥
... Or, just O(log(m))?
yosupo06 commented
Just O(log m) is enough