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.

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

complexity for searching #4

Closed
flackbash opened this Issue Oct 3, 2016 · 2 comments

Comments

Projects
None yet
2 participants
@flackbash
Copy link

flackbash commented Oct 3, 2016

The Readme suggests that this algorithm has a O(1) time complexity for searching.
However, every other source I read so far about time complexity of tries claims that the complexity is O(M) for searching where M is the maximum length of all inserted words. Which also does make more sense to me intuitively because in my imagination, the algorithm works like this: for every letter in the prefix I enter, the algorithm takes the corresponding path in the tree. This means it has to follow at least the number of letters in my prefix and at most M edges.
Can you explain to me where (or if) I'm wrong here?

@thep

This comment has been minimized.

Copy link
Contributor

thep commented Sep 5, 2017

Surely you are not wrong. The intention of O(1) statement is to claim that it's not dependent on the database size, just like how hash table does similarly on non-colliding cases, despite the fact that it still takes O(m) on hash function evaluation.

Anyway, I agree to add some more precision to the description. Let me revise it like this:

Before:

Trie is a kind of digital search tree, an efficient indexing method with O(1) time complexity for searching.

After:

Trie is a kind of digital search tree, an efficient indexing method in which search time is independent of database size. It only takes O(m) search time, where m is the length of the search string.

@thep thep closed this in 20490c0 Sep 6, 2017

@flackbash

This comment has been minimized.

Copy link
Author

flackbash commented Sep 6, 2017

Thanks a lot for the clarification!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment