In my opinion cost function is one of the parameter of complexity in reference to signal processing.

Might complexity in this scope mean algorithmic complexity in digital signal processing? However, im not really sure about this.

Complexity in signal processing normally means the computational complexity means the resources efficient utilization and over all processing speed of an algorithm...

An exponential growth in computation power led many researchers to ignore computational complexity considerations. After all, the computational power of our mobiles phones is many time that of apollo 13.

In reality, reducing computational cost/complexity ables one to fit-in many more algorithms on a single core/chip/FPGA enabling implementation with lesser resources. If 2000 GPU cores can run 10 copies of algo A and 20 of algo B, where B is slightly inferior than A, in many scenarios industries would prefer B over A.

NLMS are prefered over RLS in adaptive filtering applications (echo cancellation, system identification), despite NLMS being inferior to RLS.

Never heard of it. There are two possibilities that come to mind. The almost trivial example is dealing with "complex" signal processing (I,Q) if there's any misunderstanding about where the term "complexity" came from. The other could be from "computational complexity" which is about dealing with assessing if computing certain things is, in a broad sense, difficult/time-consuming/resource-consuming. But this is generally not "signal processing" so much. Otherwise there's a lot of stuff that's "complex" but not further defined or formalized I believe. The notion of tying "complexity" to "resource hungry" is fine but not well defined I believe.

maybe this could help 

Measures of Complexity in Signal Analysis

Many Thanks Manuel, I´ll search literature in measurement in signal proc.

Best Regards.