I wonder if the following implementation would qualify as n

Unreal Courses Talk
,
#1

First, of all n log n seems to be the fastest algorithm if we don’t use additional data structures, but I wonder if this impementation on n would make sense:

  1. Create array of 26 empty elements (or the initial value of each element could be anything out of lowercase a-z range)
  2. create an map of sorted alphabet (i.e, a->0, b->1, etc).
  3. Loop through the letters in the isogram and place each letter in the array element corresponding to alpahbetical order (example: bad b goes to 1, a goes to 0, d goes to 3).
  4. If when placing a letter, the place in the array is already “occupied”, this is not an isogram.

Would this be considered a sort of n + (array and map creation logic) operation, and thus closer to n?
THoughts?

#2

hahaha, nevermind, just watched the rest of the video. Ooops;)

#3

An important distinction that I’m not sure @ben addressed in the lecture is that Big O notation represents complexity of an algorithm not necessarily the speed of one. I.e. it represents how well the algorithm scales.

2 Likes
#4

I actually think this is a brilliant suggestion. I was pondering on the problem and the slow part in the n^2 method is the comparisons, where in the n log n method the slow part is the sorting of the entire list before starting a quick comparison. As the alphabet itself is already presorted in ascII or Unicode depending on your OS, you could quickly reduce that to a number between 0 and 25. Use that to choose a specific bit in a int32 variable. Check if that bit is flipped, If it is not flipped (IE 0) flip it, and if it IS flipped end the check as you have proven the word is NOT an isogram.

Privacy & Terms