[HammadB]

Sure, I see. I think this is an area where complexity analysis doesn’t lead to useful information.

To be more correct it’s O(N/C log C) where C is the capacity of a segment. In this case you can ignore 1/C and log C as constant. So now sure, you actually just have O(N). But this is not super useful as it says that a segmented hnsw approach and brute force approach are the same - when this is really not the case in practice.

Also O(N log N) > O(N) so I’m not sure why we would ever do anything with segmentation according to that analysis if it were correct.

[jbellis]

> I’m not sure why we would ever do anything with segmentation according to that analysis if it were correct.

What's your alternative when you can't build an index larger than C?

[HammadB]

If segmented hsnw indices were O(N log N) - it would make no sense to build the index at all - brute force would be better as O(N log N) > O(N)