retagged by
396 views
0 votes
0 votes
If I take a problem instance in unary representation then will the algorithm take exponential time and what if the problem instance is converted into binary representation then will the time complexity remain same or will it be polynomial in time ?
retagged by

1 Answer

0 votes
0 votes

If you change the encoding of the input, you've changed the formal definition of the problem, which means it's a different problem. The complexity of the original problem doesn't change

Related questions

0 votes
0 votes
3 answers
1
radha gogia asked Jun 29, 2015
719 views
Though the parent node is maximum of both the child nodes but still the procedure we follow is chosing the minimum at each step and adding them to produce a parent node, ...
0 votes
0 votes
2 answers
3
radha gogia asked Aug 5, 2015
2,139 views
Does it tale constant time or the time taken proportional to search in the entire partition of elements to find whether the component lies in that same component or not ?...