Complexity Analysis of Annoy: Construction & Query (cc Erik Bernhardsson)

[Priyanshu Singh]

Hi everyone,

I’m currently using Annoy for a research project and would like to accurately cite its performance characteristics. I’ve read through the README and source code (https://github.com/spotify/annoy), but I haven’t found a clear statement of the time complexities for:

1. Index Tree Construction (building the forest / random projection trees)

2. Search/Query Time 

@ErikBernhardsson, as the primary author of Annoy, could you please confirm the expected big-O complexities for the same.

Thanks in advance for your help!

Best regards,
Priyanshu Singh