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

The time complexity of Binary Search Tree is not precise. #11

Open
lucaspk opened this issue Jul 22, 2020 · 1 comment
Open

The time complexity of Binary Search Tree is not precise. #11

lucaspk opened this issue Jul 22, 2020 · 1 comment

Comments

@lucaspk
Copy link

lucaspk commented Jul 22, 2020

The Time Complexity for Binary Search Tree (BST) basic operations (Insert, Remove and Search) is not O(log n) if the BST is unbalanced (is O(logn) only when we are talking about Balanced BST such as AVL and Red-Black). The correct time complexity would be O(h) where h is the height of the BST. It is h because the BST may become skewed as the following image.

image
@DhruvDoshi
Copy link

Well I'II look into this and get back to you

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@lucaspk @DhruvDoshi