documentation time complexity wrong
- Dominant language
- C++
- Stars
- 16
- Forks
- 50
- PR merge metrics
- No merged PRs in 30d
Description
- 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)`.
- 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` and `interval_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` and `interval_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)` and `insert(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` and `interval_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` and `interval_maps ^= interval sets/interval maps` have wrong time complexity.
Contributor guide
No contributing guide indexed for this repository
Research direction
Review the linked Complexity, Addition, Subtraction, Insertion, Intersection, and Symmetric Difference documentation pages, focusing on the named time-complexity tables. Compare each listed operation with the corresponding single-segment and container operations, then update the incorrect table entries and verify that all affected tables use consistent complexity notation.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- documentation
- Issue type
- Documentation
- Difficulty
- 3/5
- Estimated time
- 1-2 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 45/100