I work on PAPR reduction algorithms in post-OFDM waveforms such as FBMC, etc. Actually, it depends on how you solve the minimization problem. If it is QCQP/SOCP then it has mammoth complexity but yields optimal performance. Instead, if you go for some iterative methods such as POCS, gradient method etc, then complexity is less but they offer sub-optimal performance.
Please refer to my papers on complexity of tone reservation to get more clarity on your question.
Conference Paper Reduction of PAPR of FBMC-OQAM systems by dispersive tone re...
Article Quasi-Optimal Tone Reservation PAPR Reduction Algorithm for ...
Conference Paper A Low Complexity PAPR Reduction Algorithm for ATSC 3.0 Transmitters
I did a similar analysis on complexity of SLM and PTS complexity in FBMC-OQAM and refer the article below to get better understanding
Article Reducing the PAPR in FBMC-OQAM systems with low-latency trel...
If you need any more information, don't hesitate to ask me.