4 ms·
Input length in binary is the standard way to calculate computational complexity. Sometimes we handwave that away, but in problems like this where the size of t
by ufo 5y ago
Input length in binary is the standard way to calculate computational complexity. Sometimes we handwave that away, but in problems like this where the size of the number matters, we stick to the more strict definition of computational complexity.
Number in binary vs number in decimal doesn't make a big difference because it's just a constant factor.
- zelphirkalt 5y agoThanks really. I guessed as much. What about the other questions? How do you get to an input length from a list of numbers? Just concattenate all their binary digits? Can you answer any of these?
- Sharlin 5y agoSimply the space it would naively take in memory, ie. the sum of the sizes of the elements. Which is the same thing as the length of all the elements concatenated.
- Tyr42 5y agoWe could instead specify the length (in characters) of a json list representing the two inputs: "[[1, 17, 8], [2, 6, 9]]" if we wanted to. It's base ASCII (i.e. 128 I guess), but unambiguous, and the same up to a multiplicative constant, right? That solves needing to figure out an encoding scheme for arbitrary length binary number lists. Or use a trinary encoding, with the set {"0", "1", ","} to let you list numbers nicely if you want. It doesn't matter that much.
- aliceryhl 5y agoIt doesn't really matter. Use 11 for 1, 00 for 00 and 01 for next number. Most ways you can come up with have the same length up to multiplying with some constant, and the constant does not matter in the analysis.