normally, what is the computational complexity for feasibility problem?
I’m afraid I don’t have that information. I’m afraid you’ll have to do a literature search on the topic. The standard algorithms CVX uses are symmetric primal-dual interior-point methods. Searching for papers on SDPT3 and SeDuMi in particular should help.