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 ? Algorithms algorithms time-complexity + – radha gogia asked Jul 17, 2015 retagged Jun 30, 2022 by makhdoom ghaya radha gogia 396 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
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 Rohan Ghosh answered Jul 18, 2015 Rohan Ghosh comment Share Follow See all 3 Comments See all 3 3 Comments reply radha gogia commented Jul 18, 2015 reply Follow Share I am not convinced with your solution so can u plz clarify it again . 0 votes 0 votes Rohan Ghosh commented Jul 18, 2015 reply Follow Share https://books.google.co.in/books?id=QhYZuSAb-FIC&pg=PA265&lpg=PA265&dq=does+changing+the+encoding+from+unary+to+binary+affects+complexity?&source=bl&ots=w965MGiVfP&sig=iQUMQcHRxdWMVqZLyCNtuoa5VMw&hl=en&sa=X&ved=0CEEQ6AEwBmoVChMI7MjKq6HlxgIVygqOCh2F7gC2#v=onepage&q=does%20changing%20the%20encoding%20from%20unary%20to%20binary%20affects%20complexity%3F&f=false 0 votes 0 votes radha gogia commented Jul 19, 2015 reply Follow Share If say I am having a binary number as an input and I have to convert it into unary number so how come it will take exponential time ? 0 votes 0 votes Please log in or register to add a comment.