My vote for BIg O, n

Unreal Courses Talk
,
1

I was going to say (n log n) until I read through the suggestions and found andrvalg’s suggestion.

To summarize the idea is to simply go through the word one letter at a time and drop it into a “box” with one box for each letter. if when you go to drop the letter in the box, the box is already full, end the check as the word is NOT an isogram. If you process all the letters and never come to an empty box, the word IS an isogram. Just as a quick note, no isogram could be longer than 26 letters so we do have a max w could look at as a possible end limit though I don’t know what the actual longest isogram currently in use is.

My take on the function:

  1. assume input for function is WORD. (possible isogram word)
  2. Declare a single int32 variable, IsogramCheck and initialize to 0.
  3. Declare flag bool, IsIsogram and initialize to TRUE. 3. Set up a while loop to pull letters off word in order from beginning to end as long as
    IsIsogram is TRUE && there are letters to pull from Word.
  4. take ascii value of letter - 97 (reduces value to 0 for a, 1 for b, 2 for c etc.)
    5 compute 2 ^ (value of line 4) gives results of 1,2,4,8, etc (bitwise values).
  5. do a bitwise and, Isogram & (Value of line 5),
    if true, set IsIsogram FALSE,
    if false, add (value from 5) to IsogramCheck.
  6. after while completes, return NOT value of IsIsogram.

I’m sure there are bitwise operators in C++ that could flip the bit and compute the bit faster than the decimal math version I suggest here but the it’s minor in that the method only requires a single pass (or n) through the word to check if that word is an isogram.

3 Likes
2

Well done writing such a detailed response.

3

Wow, I actually wrote the function in advance during previous videos and I chose the naive implementation with O(n^2). Now I thought about using some sort of hash map, so I searched thru docs and found std :: map :: find but that seems to have log n complexity as well, so no real improvement there. But your answer might be actualy O(n) which is quite interesting. Well done :sunglasses:

2 Likes
4

Yes, exactly. It is easier than bit-fiddling though. Just have an array that maps to the char values for 'a' … 'z', something called UsedLetter[], say.

Initializing the array and other initialization only costs constant times. Then the key operation in the loop over the guess letters is

if (LetterUnavailable[CurrentGuess[i]++) return false;

using if and n++ trickiness as a little puzzle.

Note that one can also restrict alphas from other characters by prefilling the non-permitted char-code positions in a CharUnavailable[256] with 1’s where a character is not OK at all and 0 where permissible single alphas can occur.

To make this case-insensitive I would also do

if (CharUnavailable[ tolower( CurrentGuess[i] ) ]++ ) return false;

Now, since N cannot be more than 26 (for English anyhow), this is really all O(1). That is, there is a constant that bounds the time to check for an isogram given a CurrentGuess of any length.

And that explains why it doesn’t matter if you take n (n-1)/2 either. As far as big-O goes, there is a constant ceiling and brute force for small n is simply good enough and probably better than all the fussing to make it run in c+k*n operations since c may dominate small n :wink:.

Added after Lecture 42

Of course, O(1) was not on offer. And thinking about growth when there is no near ceiling is very important and where big-O matters.

But when there is a low ceiling, the trade-off over simplicity and understandability becomes important too, along with appreciation of the constant factors.

Nice discussion here.

1 Like
5

I thought of the same solution as JennBren and this is my implementation

int32 hash = 0;
for (int32 i = 0; i < guess.length(); i++)
{
	int32 mask = 1 << (guess[i] - 'a');
	if ((mask&hash) != 0) 
	{
		return EWordStatus::Not_Isogram;
	}
	else
	{
		hash |= mask;
	}		
}
6

I do believe the best Big O notation we can get to for this game is O ( n ), since we need to go through the entire word (at least) in order to obtain any answer, and nothing less. We can’t do bisection search or recursion to cut down on time which would make use of log related notations.