Can-Do-Anything-In-O(log n)-Datasequence(TM)
These are the time complexity requirements for a DS of size n. Each element has a 'value' which is Less Than Comparable and can be 'accumulated' (i.e., the elements can be "summed up"). Furthermore, elements don't change their position, but may change their values. This has to be possible in O(log n), too.
Creation: O(n)
Split: O(log n)
Concatenate: O(log n)
Reverse: O(log n)
Find minimum: O(log n)
Find sum: O(log n)
Furthermore, a Forward Iterator with O(1) amortized time to go to the next element has to be provided.
I just finished implementig such a DS. However, it could be... nicer (especially the iterator, which requires O(log n) space). So just out of curiosity, what would you do to achieve these time bounds?
Creation: O(n)
Split: O(log n)
Concatenate: O(log n)
Reverse: O(log n)
Find minimum: O(log n)
Find sum: O(log n)
Furthermore, a Forward Iterator with O(1) amortized time to go to the next element has to be provided.
I just finished implementig such a DS. However, it could be... nicer (especially the iterator, which requires O(log n) space). So just out of curiosity, what would you do to achieve these time bounds?
Topic archived. No new replies allowed.