True, and the OP's isn't really O(N²) either. Both should factor in the length of the string. Both should factor the growth of the array/hash. Mine should also factor in bucket collisions when talking about worst case.

So, the OP's is O(N² * L * O(Growth(N))) and mine is O(N * L * O(Growth(N))). I chose to ignore the common (and thus irrelevant) factor, even if accuracy suffered a little.

I think that you're still missing the lookup into the hash, which isn't a constant time operation and can't be factored out because the OP doesn't have it. Since the best you can do with such a lookup is O(log(N)), IMHO the complexity in your case is at least O(N * log(N)).

Flavio
perl -ple'$_=reverse' <<<ti.xittelop@oivalf

Don't fool yourself.

Doesn't the number of buckets grow with the number of elements in the hash? If so, why would it take longer as more elements are added? The number of elements in a bucket should remain less than some bound, no? O(bound) = O(1). I don't know how hashes are implemented specifically in Perl, but I heard they were O(1) for lookup. (Again, not worse case.) Wikipedia says the same for hashes in general:

Hash tables are often used to implement associative arrays, sets and caches. Like arrays, hash tables provide constant-time O(1) lookup on average, regardless of the number of items in the table. (O(1) means that it takes a constant amount of time independent of the number of items involved.)

From where did you get O(log N)?