re: Daily Challenge #3 - Vowel Counter VIEW POST

TOP OF THREAD FULL DISCUSSION
re: The most efficient structure for this sort of lookup would be a binary tree, which has a O(log n) complexity for lookup, so such a solution would b...
 

We don't care about the vowels being ordered for this problem, so you'd be paying extra time (vs. a hash-based set, or just hard-coded equality checks) for a property you're not using.

I don't think so. Consider pseudocode like this:

if (letter == 'a' ||
    letter == 'e' ||
    letter == 'i' ||
    letter == 'o' ||
    letter == 'u') {
  vowels += 1;
}

Given the character 'u', it would do 5 comparisons, where the worst case for a binary tree would be 3. Cases where the letter isn't a vowel will involve 5 checks as well.

Edit: fixed the number of comparisons.

You also have to traverse the tree to get to the next letter. But I see what you mean. Only counting equality checks, hard-coding behaves like a linear search. My bad.

I think you might still be missing Brian's point that a hash set has O(1) lookup time, which is faster than the tree set's O(log n).

(On paper. Real-world implementations vary. e.g. Ruby's hashes just do linear search at this size.)

code of conduct - report abuse