Complexity applies to parsing algorithms as to any other. Any parser will take a time which varies in some way on the complexity of its input. Hence one could try to infer the nature of the human parser by looking at how the time taken to respond to sentences varies with the input. I haven't found any references to this, but I think some psycholinguists have tried it.