33rd Friday Fun Session (Part 2) – 15th Sep 2017
The complexity for FaaS solution is O(n), where n is the largest day number. It looks like polynomial. However, it is actually pseudo-polynomial.
Size of input
Complexity is measured in terms of the size of input, say, in bits. Suppose, there are b bits in n. Then O(n) = O(2b) and hence, it is exponential.
Let’s assume n increases from 10 to 1125899906842624. More specifically, lunch schedule, as used in the previous example, changes from 1, 3, 4, 5, 6, 7, 10 to 1, 3, 4, 5, 6, 7, 1125899906842624. We still have the same 7 days to go for lunch. Yet, we are running 1,125,899,906,842,624 loops. In our layman understanding, the problem is still the same and should have taken the same amount of time to execute, and yet, for the latter, the algorithm takes way too long!
Spot a pseudo-polynomial
This is how we spot a pseudo-polynomial time algorithm. Ideally, we would like to express the complexity using the number of inputs; here, it should have been 7. But the above algorithm works in a way, where the complexity has been expressed in one of the numeric values of the input, the maximum value of the input – 1125899906842624, to be precise. This is where we are tricked into believing it to be a polynomial time algorithm, linear (polynomial) in the (max) numeric value of the input. But if we apply the definition of complexity that takes into consideration the size/length of the input, then it is actually exponential.
To be more specific, if we look at the input size, 4 bits are required to represent 10, while 50 bits are required to represent 1,125,899,906,842,624. Complexity has gone from O(24) = 10 loops to O(250) = 1,125,899,906,842,624 loops.
That is essentially exponential in the number of bits, meaning exponential in the size of the input but polynomial in the numeric value of the input. Algorithm with this kind of running time is called pseudo-polynomial.
Truly polynomial
At this point, you might wonder what is a truly polynomial time algorithm. For example, when we add n numbers using a loop running n times, we say, the complexity of it to be O(n). But here this n can also be written as 2b. So, shall we also say, adding n numbers is a pseudo-polynomial time algorithm?
Well, when we say, adding n numbers, we implicitly say, we want to find the sum of n 32 bit numbers/integers. Then the size of n numbers is 32 * n. Once again, the formal definition of complexity is defined in terms of input size, in bits. What is the input size here? The size here is 32n. The complexity is O(32n) and removing the constant terms it is O(n), a truly polynomial time algorithm.
Sharing Experiences 