boostorg / boostorg/icl

documentation time complexity wrong

Open
#45 0 comments 0 reactions 0 assignees View on GitHub
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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.