what is the space and time complexity (lookup, insertion) of count-min sketch and quotient filter?
I could not find these complexities. I would like to make a program which find the frequencies of objects in a set in the fastest way, so the time complexity is really important for me.
I read the research article about those objects, about quotient filter from "Don’t Thrash: How to Cache your Hash on Flash", it was said there that its lookup and insert actions are faster than bloom filter which is O(k) (k is number of hash function).
I also read from "Count-Min Sketch" and "An Improved Data Stream Summary: The Count-Min Sketch and its Applications" but could not find the big O complexity of both of these data structures.