I have added let's say n number of strings in an ordered set of strings,

set<string>

now i use the find method to find a string, what should be the time complexity of this operation. For integer set it is logn , so will it be size of string searched* logn for this? If possible please give an explanation too .

CodePudding user response：

According to the std::set man page:

Complexity:
Logarithmic in the size of the container.

So that would be O(log(N)). (The reason behind that is that std::set is typically implemented by a binary-tree type of data structure, and a root-to-leaf traversal of a binary-tree with N nodes takes O(N) steps)

CodePudding user response：

std::set<T>::find performs O(log(n)) comparisons regardless of the type T.

You might be confused since comparing two integers has constant time (i.e. O(1)) complexity, but comparing strings is linear (i.e. O(N)). But this has no bearing on the number of comparisons the set performs. So you are right that the find on a set of strings performs length of the string * log(N) operations.