N log n? Is plain n possible?

Hi all,

So I am somewhat confused with this lecture, and I have a few questions to clear it up.

  1. Is “n log n” just reordering it like you talked about? (turning boom into bmoo and then checking bmoo) I have no clue what “log” does because I’m just starting Alg. 2 this school year.

  2. I don’t understand how plain “n” could be possible. Is it possible, or is it not being possible a point that Ben is trying to make?

I’m not sure, but I think that “n log n” is the best solution here for isogram checking. I’ll look at the next video to see if it reveals anything to me.

Thanks,
Aidan M.

Edit: There was a small part I missed (that it was “n log n plus n” at around 8 mins), I understand now, thanks.

Edit 2: I also had trouble with understanding what you meant by O(n), I thought about having an array or something of the alphabet on file to compare with.

log is short for logarythm,

I believe that (n log n) does not take into consideration the additional check for pairs. Just N is the checking for pairs. Just N therefore is not a valid check since its just comparing neighbor values and can not properly check for isograms. (n log n) + n would have to be the fastest sort to actually take into account the value checking for an isogram.

1 Like