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
Complexity - 1.84.0 (https://www.boost.org/doc/libs/1_84_0/libs/icl/doc/html/boost_icl/implementation/complexity.html )
In "Table 1.15. Time Complexity of Addition", interval set/separate interval set/split interval set/interval map/split interval map += interval_sets/interval_maps 's time complexity is O(m log(n+m)), but this time complexity should be at least interval set/separate interval set/split interval set/interval map/split interval map += T::segment_type 's time complexity (O(n)). Example: the interval_sets/interval_maps contains only one big interval (whose type is T::segment_type), and this interval makes interval set/separate interval set/split interval set/interval map/split interval map += T::segment_type 's time complexity O(n).
Complexity - 1.84.0 (https://www.boost.org/doc/libs/1_84_0/libs/icl/doc/html/boost_icl/implementation/complexity.html )
In "Table 1.15. Time Complexity of Addition",
interval set/separate interval set/split interval set/interval map/split interval map += interval_sets/interval_maps
's time complexity isO(m log(n+m))
, but this time complexity should be at leastinterval set/separate interval set/split interval set/interval map/split interval map += T::segment_type
's time complexity (O(n)
). Example: theinterval_sets/interval_maps
contains only one big interval (whose type isT::segment_type
), and this interval makesinterval set/separate interval set/split interval set/interval map/split interval map += T::segment_type
's time complexityO(n)
.Addition - 1.84.0 (https://www.boost.org/doc/libs/1_84_0/libs/icl/doc/html/boost_icl/function_reference/addition.html )
In "Table 1.23. Time Complexity for inplace Addition on interval containers",
interval_set/separate_interval_set += interval_sets
,split_interval_set += interval_sets
andinterval_maps += interval_maps
have wrong time complexity.Subtraction - 1.84.0 (https://www.boost.org/doc/libs/1_84_0/libs/icl/doc/html/boost_icl/function_reference/subtraction.html )
In "Table 1.26. Time Complexity for inplace Subtraction on interval containers",
interval_sets -= interval sets
andinterval_maps -= interval sets/interval maps
have wrong time complexity.Insertion - 1.84.0 (https://www.boost.org/doc/libs/1_84_0/libs/icl/doc/html/boost_icl/function_reference/insertion.html )
In "Table 1.29. Time Complexity for inplace insertion on interval containers",
insert(interval_set/separate_interval_set, interval sets)
,insert(split_interval_set, interval sets)
andinsert(interval_maps, interval maps)
have wrong time complexity..Intersection - 1.84.0 (https://www.boost.org/doc/libs/1_84_0/libs/icl/doc/html/boost_icl/function_reference/intersection.html )
In "Table 1.36. Time Complexity for inplace intersection on interval containers",
interval_sets &= interval sets
andinterval_maps &= interval sets/interval maps
have wrong time complexity.Symmetric Difference - 1.84.0 (https://www.boost.org/doc/libs/1_84_0/libs/icl/doc/html/boost_icl/function_reference/symmetric_difference.html )
In "Table 1.39. Time Complexity for inplace symmetric difference on interval containers",
interval_sets ^= interval sets
andinterval_maps ^= interval sets/interval maps
have wrong time complexity.The text was updated successfully, but these errors were encountered: