Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

StrictStack / StrictQueue sizeInfo time/space complexity #28

Open
jnape opened this issue Dec 12, 2020 · 0 comments
Open

StrictStack / StrictQueue sizeInfo time/space complexity #28

jnape opened this issue Dec 12, 2020 · 0 comments
Assignees
@jnape
Labels
enhancement
Milestone
alpha-3

Comments

@jnape
Copy link
Member

jnape commented Dec 12, 2020

Currently both StrictStack and StrictQueue use an amortized O(1) time cost and O(1) space cost for their sizes. If StrictStack could gain an O(1) time/space complexity, and if StrictQueue delegated to StrictStack, it would achieve the same complexity. This should be doable with a single additional wrapper node in StrictStack that was carried the size along with the spine.
@jnape jnape modified the milestones: alpha-1, alpha-2, alpha-3 Dec 12, 2020
@jnape jnape self-assigned this Dec 12, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@jnape jnape

Labels
enhancement
Projects
None yet
Milestone
alpha-3
Development

No branches or pull requests
1 participant
@jnape