Time complexity of this algorithm in Big(O)

  c++, time-complexity

I came up with the following algorithm to calculate the time complexity to find the second most occuring character in a string. This algo is divided into two parts. The first part where characters are inserted into a map in O(n). I am having difficulty with the second part. Iterating over the map is O(n) push and pop is O(log(n)). what would be the BigO complexity of the second part ? finally what would the overall complexity be ? Any help understanding this would be great ?

void findKthHighestChar(int k,std::string str)
{
    std::unordered_map<char, int> map;
    
    //Step 1: O(n)
    for (int i = 0; i < str.size(); i++)
    {
        map[str[i]] = map[str[i]] + 1;
    }

    //Step2: O(n*log())
    //Iterate through the map
    using mypair = std::pair<int, char>;
    std::priority_queue<mypair, std::vector<mypair>, std::greater<mypair>> pq;
    for (auto it = map.begin(); it != map.end(); it++) //This is O(n) .
    {
        pq.push(mypair(it->second, it->first)); //push is O(log(n))

        if (pq.size() > k) {
            pq.pop();                           //pop() is O(log(n))
        }
    }
    std::cout << k << " highest is " << pq.top().second;
}

Source: Windows Questions C++

LEAVE A COMMENT