## 33rdFriday 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.

Index

## 33rdFriday Fun Session – 15th Sep 2017

Given a lunch schedule – a sequence of days when lunch is planned, and three price plans – daily, weekly and monthly, we want to get the cheapest lunch price.

This is the solution to JLTi Code Jam – Aug 2017 problem.

### Let us walk through an example

Let us take an example as mentioned here: 1, 2, 4, 5, 17, 18. Since first day is 1 and last day is 18, it can be put under a month that consists of 20 consecutive days (not calendar month). We can use a monthly plan. But it would be too expensive (S\$ 99.99) for just 6 days.

The days: 1, 2, 4 and 5 fall within a week that requires consecutive 5 days (not a calendar week). We have an option to buy a weekly plan for these 4 days that would cost S\$ 27.99. However, that would be higher than had we bought day-wise for 4 days at a price of S\$24.

### Dynamic Programming

In general, at any given day, we have three options:

1. We buy lunch for this day alone, using daily price S\$ 6. Add that to the best price found for the previous day.
2. We treat this as the last day of a week, if applicable, and buy a weekly plan at a cost of S\$ 27.99. Add that to the best price for the day immediately prior to the first day of this week.
3. We treat this as the last day of a month, if applicable, and buy a monthly plan at a cost of S\$ 99.99. Add that to the best price for the day immediately prior to the first day of this month.

This is an optimization problem that can be solved with dynamic programming where we use the result of already solved sub-problems.

### Bottom-up

We have two options: top-down and bottom-up. We realize that, at the end, all the sub-problems (for each of the days) have to be solved. We also find that it is easy to visualize the problem bottom-up. And if we do use bottom-up then the required space would be limited by the last day number.

Hence, we will solve it using bottom-up dynamic programming.

Blue colored days are when lunch is scheduled.

On day 1:

Cost S\$ 6.

On day 2:

Daily basis: S\$ 6 + price at day 1 = S\$ 12

Weekly basis: S\$ 27.99

Monthly basis: S\$ 99.99

Best price: S\$ 12

On day 3:

No lunch schedule, cost of previous day S\$ 12 is its cost.

On day 4:

Daily basis: S\$ 6 + price at day 3 = S\$ 18

Weekly basis: S\$ 27.99

Monthly basis: S\$ 99.99

Best price: S\$ 18

On day 5:

Daily basis: S\$ 6 + price at day 4 = S\$ 24

Weekly basis: S\$ 27.99

Monthly basis: S\$ 99.99

Best price: S\$ 24

From day 6 to day 16:

No lunch schedule, cost of previous day will be carried forward: S\$ 24.

On day 17:

Daily basis: S\$ 6 + price at day 16 = S\$ 30

Weekly basis: S\$ 27.99 + price at day 12 = S\$ 51.99

Monthly basis: S\$ 99.99

Best price: S\$ 30

On day 18:

Daily basis: S\$ 6 + price at day 17 = S\$ 36

Weekly basis: S\$ 27.99 + price at day 13 = S\$ 51.99

Monthly basis: S\$ 99.99

Best price: S\$ 36

Finally, the best price is S\$ 36.

### Another example

Let us work with another example: 1, 3, 4, 5, 6, 7, 10.

On day 7:

Daily basis: S\$ 6 + price at day 6 = S\$ 36

Weekly basis: S\$ 27.99 + price at day 2 = S\$ 33.99

Monthly basis: S\$ 99.99

Best price: S\$ 33.99

Finally, the best price at the end is S\$ 39.99.

### Complexity

The complexity is O(n), where n is the largest day number. It is a pseudo-polynomial time algorithm.

GitHub: FaaS

Index