Asked By : Mark
Answered By : nyan nyan nyan
Let T : N → N. A Turing Machine M has time complexity T(n) if $∀ x ∈ {0, 1}^*$ , M(x) halts in at most T(|x|) steps.
That is to say, time complexity captures the (relative) amount of time taken for all inputs. Thus the answer is no, that doesn’t change the time complexity at all, because then you would just have an instance of the question: Given a graph $G(V’,E)$, where $|V’| = m$, and an integer, $k$, determine if a clique with size $k$ exists. As $m$ increases, the running time would increase in the way similar to how it would if |V| increases in the original problem. However, if $m$ is defined to be a constant, then the time-complexity would be $O(1)$ (the TM would halt in at most x steps no matter what the graph is) but the problem itself would not make any sense
Given a graph G(V,E), and k-integer, determine if a clique with size k exists after checking m vertices, where m is a constant.
because a decision problem is formally defined in terms of set-membership, and a different algorithm (a different way to finding if a clique exists) would yield a different result, for $|V| > m$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/44951
