Week 8, The Max Slice

This week in class we covered more on Big O, omega, and simplifying different functions. A challenge for this week was to simplify an original max_slice program given by Larry. I simplified it down to both O(n²) and O(n).

The problem:

Take original max_slice program which runs on O(n³) and simplify it into both O(n²) and O(n).

Is this accomplishable?

Yes. The given statement is a lot more complex than it needs to be.

Devising a Plan

Finding the Connection:

It appears that a major problem with the complexity within the code is that they are not using some of the functions already defined within python, such as max.

Carrying out the Plan:

The goal was to eliminate a loop. I did this by instead of sorting based on max length in each section, just using the built in function max.

Next I had to eliminate one more loop. I added a variable in order to keep track of additional info I would need to record. I used the max function again in order to keep track of another variable to check if the max sum would increase by adding a number.

Looking Back

Examine the Obtained Solution:

Eventually I got what I call the Golden Sum, it seems to work for all numbers and instead of O(n³) or O(n²) it is just O(n) which is as simple as it gets because there is no way this could be done in any O less.