Maybe I am missing something but I think O(N * N) is the correct complexity for a nested loop implementation. If you believe that is wrong, can you explain a bit more?
Well that assumes the same cardinality for both sides of the join, which may be far from the case, especially if selections can be pushed down to scans.