I thought about sorting using hash map, and the time complexity of insert operation is O(log(n)) so, I am wondering is it possible to sort using O(log(n) n)?

//sahil L. Totala 
#include <bits/stdc  .h>
#include <iostream>

using namespace std;
int main ()
{
  
  cout << "how much no. do you want:";
  int n;

  map < int, int > mp;

  cin >> n;

  for (int i = 0; i < n; i  )
    {
      int k = 0;
      cin >> k;
      mp.insert ({k, 1});
    }

  for (auto itr = mp.begin (); itr != mp.end ();   itr)
    {
      cout << itr->first << endl;
    }

  return 0;
}

CodePudding user response：

As it stands right now, the code is something like O(N log M), where N is the total number of input elements, and M is the number of unique elements.

You're attempting to insert N elements into your map, but that attempt will only succeed for elements that weren't previously present. That means the map will only contain one node for each unique element in the input, so each insertion is the logarithm of the number of unique elements.

That has a bit of a problem though: as it stands now, your code doesn't really work correctly. If the input contains duplicates, only unique numbers will be written out. For example, if you sort [1 1 1 1 2 2 1 2 1], the expected output would normally be [1 1 1 1 1 1 1 2 2 2], but your code will produce only [1 2].

It is possible to fix that while retaining approximately the current complexity. The obvious one would be to change mp.insert ({k, 1}); to mp[k].

Then you'd change your output loop to something like:

  for (auto itr = mp.begin (); itr != mp.end ();   itr)
    {
      for (auto i = 0; i<itr->second; i  )
          cout << itr->first << '\n';
    }

Incrementing means we count the number of times each input value occurs. Then we write each of those values out as often as it occurred.

At least in theory, this can save us a tiny bit on complexity if we expect the input to contain a lot of duplicates.

As it stands right now, you're not really using the value you associate with each key, so you could use an std::set instead of an std::map.

Another way to fix your code would be to use a std::multiset instead, but this would change the complexity from O(N log M) to O(N log N).

As an aside, I'd advise avoiding std::endl. Just write out a new-line, as shown in the modified output loop. using namespace std; and #include <bits/stdc .h> are best to avoid as well.