Big-O complexity of finding exception handler for zero-cost exceptions
The crucial data structure here is an interval tree, that can be pre-computed at compile time, which has a complexity of $O(\log n + k)$ to find all $k$ ranges that contain a certain point, assuming there are a total of $n$ ranges. Here your ranges are exception blocks in the compiled code and your point is the instruction address.

I will assume the C++ model of one try block followed by one or more catch blocks that may or may not match a thrown exception and I will assume that a compiled program has $n$ try blocks in total.

Then when an exception is thrown it takes $\log n$ time to find the $k$ relevant try blocks in the current call frame (which we order by specificity, which is done by minimizing range size). And for each relevant try block there may be one or more relevant catch block, which may or may not match. If none match we go to our caller and search again.

But at some point we find a matching exception (or halt). The total complexity then is $O(c\log n + k)$, where $c$ is the number of calling frames we had to go up, and $k$ is the total number of relevant catch blocks that we considered for matching.

This is assuming that you do exception type matching at runtime, instead of maintaining separate tables per exception type. Since $k$ is generally very small, this is a sensible approach. You can get better asymptotic runtimes in terms of $k$, but I described a practical approach.