re: Daily Challenge #3 - Vowel Counter VIEW POST

TOP OF THREAD FULL DISCUSSION
re: Thinking the string as a Set with O(1) for look up operations: solution is O(n), where n = len(str) def count_vowels(str): vowels = "aeiouAE...
 

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 be O(n log n).

 

Not sure if I follow. O(n log n) is worst than O(n). Insertions in a binary tree are expensive to keep it balanced.
If you use a set or hashmap assuming zero collisions, the look up is O(1). Then the bottke neck is in the string iteration. Right?

I've made the assumption that the binary tree was already built, it could've been done during compile time, for instance.

As for hashing functions, you could get away with an Array where the index is the code point for a given character.

 

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