Vote for log(N), faster than n

Unreal Courses Talk
,
1

I believe if I use an ordered set that doesn’t allow duplicates with insert O(logn) and then check if the size changes to see if I had a duplicate value I could acquire const * log(N) time or just log(N)

I found a table of big O values for data structures in the STL here:
http://www.cs.northwestern.edu/~riesbeck/programming/c++/stl-summary.html

The implementation would look something like this:

bool isIsogram() {
    // somehow make the ordered set here.
    int oldSize = mySet.size(); 
    // loop and add all the chars
    mySet.insert(char);
    if (mySet.size() == oldSize)  { // if it is still the same size, there was a duplicate
        return false;
    }
    return true;
}

Please let me know whether or not this would work.

Edit:: Now that I’m thinking about it since I have to loop through all the chars it would be NlogN with this method… The fastest I guess would be to use a hashtable with constant insert time to get O(N)