BPSK and QPSK demodulation computational complexity
To demodulate BPSK and QPSK as described by the OP is to simply take the sign of the waveform (decision), which has trivial computational complexity. The real complexity lies in everything that occurs prior to decision in a practical receiver: There is typically an equalizer to remove multi-path distortion, a matched filter to optimize the signal to noise ratio at the decision locations (in the presence of white noise), an automatic gain control (AGC) loop to remove long term amplitude variation, a timing recovery loop to remove phase and frequency offsets in the timing clock (for the proper sample locations of the final decisions), and a carrier recovery loop to remove residual phase and frequency offset of the carrier frequency due to differences in the Tx and Rx clocks and Doppler due to possible motion between transmitter and receiver.
For instance, the block diagram below shows a practical receiver carrier recovery loop that also does the final decisions for QPSK; where for QPSK each decision would be a simple threshold detector on I and Q (notice the relative computational complexity of the decision block versus the rest of the loop, and this is just for carrier recovery and does not include the AGC and timing recovery operations described above that would be typical).