# approximation algorithm with polynomial complexity

It might be a silly question, I do take a carefully read about approximation algorithm through coursenotes, but when I saw the words "approximation algorithm with polynomial complexity", I can't understand what it means, I searched a lot and here is my assumption.

First, for some NPc or NP hard problem, we can try to solve them approximately, because there is no optimization algorithm right now. So compared with some opotimal solution theoretically, some optimazation problem can use approximation algorithm to get an approximation solution, such like vertex covering problem.

Then it is the term polynomial complexity, an algorithm is polynomial if for some k>0, its running time on inputs of size n is O(n^k).

So is "approximation algorithm with polynomial complexity" means an approximation algorithm that whose complexity is in polynomial time? So is it means there are approximation algorithm that has other complexity such as exponential complexity.

By the way, through the approximation algorithm for vertex covering problem, I know what the algorithm is (briefly it is takes an arbitrary edge from subset E' of all possible set of edges, add two vertax at set S and remove all edge who has the same vertex with that arbitrary edge and continue until E' is empty). But how to observe it is polynomial complexity or what?

I really apprexiate if someone can solve my confusion.

An "approximation algorithm with polynomial complexity" means just that: an approximation algorithm which complexity is polynomial. As you mentioned, an algorithm has polynomial complexity if $\exists k \mid T(n) = O(n^k)$. To ensure that your algorithm has polynomial complexity, you need to go back to the $O$-notation definition and do a proper analysis.