Skip to content

Improve average big O runtime of finding conflicts #2880

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
Merged
X9VoiD merged 2 commits into from
Aug 16, 2023
Merged

Improve average big O runtime of finding conflicts #2880

X9VoiD merged 2 commits into from
Aug 16, 2023

Conversation

@X9VoiD
Copy link
Member

@X9VoiD X9VoiD commented Aug 16, 2023 •
edited
Loading

Also significantly reduce memory overhead by not allocating any extraneous array.

Before PR

Complexity Average Worst Case
Time O(n^2) O(n^2)
Space O(n^2) O(n^2)

After PR

Complexity Average Worst Case
Time O(n) O(n^2)
Space O(n) O(n)

@X9VoiD X9VoiD merged commit 837e41b into OpenTabletDriver:master Aug 16, 2023
@X9VoiD X9VoiD deleted the config-conflict branch August 16, 2023 18:54
@gonX gonX added enhancement New feature or request tests Adds or modifies a unit test labels Nov 25, 2023
@X9VoiD X9VoiD mentioned this pull request Dec 10, 2023
Merged
@gonX gonX added the backport-added A backport is already merged label Oct 2, 2025
@gonX gonX added this to the v0.7.0 milestone Oct 2, 2025
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

No reviews

Assignees

No one assigned

Labels

backport-added A backport is already merged enhancement New feature or request tests Adds or modifies a unit test

Projects

None yet

Milestone

v0.7.0 ("Avalonia")

Development

Successfully merging this pull request may close these issues.

2 participants

@X9VoiD @gonX