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.

CodePudding user response：

The complexity of finding an ordered string in a set of strings in c will be O(n log n).

The std::set is a sorted container, so finding an element in it is a matter of doing a binary search, which is O(n log n).

The elements in a std::set are stored in a binary search tree, which means that the elements are stored in sorted order. When you search for an element in a std::set, the search algorithm will first compare the element you are searching for with the root element of the tree. If the element you are searching for is less than the root element, then the search algorithm will search the left subtree; if the element you are searching for is greater than the root element, then the search algorithm will search the right subtree. This process is repeated until the element is found or the search algorithm reaches a leaf node (i.e. a node with no children).