It is given in the notes that time complexity of consistent hashing is O(logn), where n is the number of cache shards. How is it derived?. Should it not be O(N/k) where N is the total number of cache servers & k is the total number of buckets or virtual nodes?
3 Likes
Hey @Vivek_sharma! We appreciate your comment.
The time complexity of consistent hashing is O(logn), where n is the number of cache shards. Consistent hashing uses a binary search algorithm to locate the correct cache shard for a given key. Binary search has a time complexity of O(logn). The total number of cache servers or virtual nodes does not affect the algorithm’s time complexity, as they are only used to distribute load across the cache shards evenly. Therefore, the time complexity of consistent hashing is logarithmic in the number of cache shards.
We hope Educative has inspired you to further your learning.
1 Like