search

kdn251 / interviews

Everything you need to know to get the job.
https://www.youtube.com/channel/UCKvwPt6BifPP54yzH99ff1g?view_as=subscriber
MIT License
63.67k stars 12.91k forks source link

BST incorrect time complexity #118

Open Rohithyeravothula opened 5 years ago

Rohithyeravothula commented 5 years ago

Insertion, deletion, access and search time complexities of BST are incorrect, they must be O(h) where h = height of the BST, and not O(log(n)). In cases, where BST is a balanced BST, h will be log(n) and the time complexities will be O(log(n)), else h can be n (no of nodes) in worst case so the time complexities will be O(n).

bessex commented 5 years ago

Your assumption is that the listed time complexities should be worst case though, right? Is this project intended to provide average or worst case time complexity?