4 ms·
Make sure you check out Appendix A at the end of the paper (Asymptotic Worst-Case Time Complexity), in case you imagined the name "stack" implies constant-time
by bnjmn 10y ago
Make sure you check out Appendix A at the end of the paper (Asymptotic Worst-Case Time Complexity), in case you imagined the name "stack" implies constant-time push/pop performance. This data structure is only a "stack" in the sense that it provides last-in-first-out access.
- chrisseaton 10y agoIs it possible for a contended concurrent stack accessed by an arbitrary number of threads to have guaranteed constant-time operations? I wouldn't think that was a realistic expectation.
- aidenn0 10y agoA lock-based stack can be O(M) in number of threads accessing it. Judging by the abstract (haven't read the paper) this is O(N) in the size of the stack.
- EvgeniyZh 10y ago"in terms of the number of concurrent threads in the system (N), the actual size of the stack(S) and the parameter W ... as soon as W consecutive nodes get marked ... the worst case time complexity of the pop operation is O(NWS)"