# What is an approximation factor for the Greedy Motif Search algorithm?

What is approximation factor for the Greedy Motif Search algorithm?
I couldn't find an answer to my question except for the fact that the algorithm has a unknown aproximation factor. I'm not a native speaker and there is almost nothing about it available in my first language which makes it really hard to even understand the definition of the "approximation factor" which may lead to this question that could be rather obvious to answer.

A possible algorithm is shown on page 4: http://veda.cs.uiuc.edu/courses/fa08/cs466/lectures/Lecture5.pdf

I know that there isn't a known approximation factor because sources like the book "An Introduction to Bioinformatics Algorithms" are stating it.
I haven't really formed thoughts on it, because I'm not certainly sure what the definition of approximation factor is in a case like this. What I mean is: "The approximation ratio, or performance guarantee of algorithm A is defined as its maximum approximation ratio over all inputs of size n".
I would've thought that it may be unknown due to the fact that we could have a input of infinite, which is probably not the right thought in this regard. Another thought I had was that the algorithm has no lower bound for the optimal solution.

• veda.cs.uiuc.edu/courses/fa08/cs466/lectures/Lecture5.pdf page 4 shows a possible pseudocode of the greedy motif search algorithm that I´m talking about – Y.y.y-a-ea- May 8 '19 at 16:37
• @Evil sorry I forgot to mention your name so you probably couldn´t see my answer – Y.y.y-a-ea- May 8 '19 at 16:44
• It would help to edit the question to provide that information in the question. We want people to understand what you are asking, without needing to read the comments. – D.W. May 8 '19 at 16:54
• Also, why do you think there is no approximation factor for that algorithm? What are your thoughts? Do you think there should be an approximation factor? Why? – D.W. May 8 '19 at 16:55
• @D.W. I edited my thread/post a little bit now so it should provide a bit more information on my thoughts and my problem + the source that I´ve used. – Y.y.y-a-ea- May 8 '19 at 17:09

Using proof by Kaplan and Shafir3 author shows that $$\mid t_{greedy}\mid = 3.5 * OPT(S)$$.