You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
The implementation of Chip<M>::generate_trace for RangeCheckerChip<MAX>, in range/src/lib.rs, is O(MAX * log(|self.count|)) but can be done in O(|self.count| * log(|self.count|)). In this context, self.count is a BTreeMap<u32, u32> whose key space is 0..MAX. This means that |self.count|, the cardinality or number of keys of self.count, is less than or equal to MAX, and thus the algorithm is asymptotically slow, as noted by the code comment.
The text was updated successfully, but these errors were encountered:
The implementation of
Chip<M>::generate_trace
forRangeCheckerChip<MAX>
, inrange/src/lib.rs
, isO(MAX * log(|self.count|))
but can be done inO(|self.count| * log(|self.count|))
. In this context,self.count
is aBTreeMap<u32, u32>
whose key space is0..MAX
. This means that|self.count|
, the cardinality or number of keys ofself.count
, is less than or equal toMAX
, and thus the algorithm is asymptotically slow, as noted by the code comment.The text was updated successfully, but these errors were encountered: