Approximate String Matching in RDBMS

Does someone know what is the best theoretical complexity in the literature, as O(f(N)), where N is the number of rows in a table t and
where approximate string matching on some field in t is to be done.

I am not asking about the complexity of a single approximate match between 2 strings with lengths n and m, but on the cost of the lookup over the entire table.
In other words, what is the cost of the following, in terms of N, the number of rows in t:

SELECT * FROM t WHERE APPROXIMATELY_EQUAL(t.a, threshold)