in reply to Re: elsif chain vs. dispatch

in thread elsif chain vs. dispatch

To be pedantic, that's not true.When you say that something is O(N) or O(N^2) or whatever, you are saying that as N changes then the resource in question (time or memory normally) changes with that relation to it. So if something is O(N) and N doubles, then the time taken doubles.

`O(N)`means that the growth is

*at most*linear.

`O(N^2)`means that the growth is

*at most*quadratic. This means that any algorithm that is

`O(N)`is also

`O(N log N)`and

`O(N^2)`.

If you want to express that an algorithm is linear (and not worst case linear), the correct function is use is called `Θ`.

Note also that hash lookups are, worst case, `Θ(N)`. There's always a chance that all hash keys map to the same value, resulting in a linear list that needs to be searched.

In Section
Seekers of Perl Wisdom