Leo's Big(O) blog

ciWhen we talked about the running time of an algorithm we mentioned the avarage cost on an algorithm, but we said that it was very hard to estimate it. In amortized analysis, we are going to avarage an estimate number of sequeneces on a data structure, WITHOUT using probability. The 3 main methods for calculating the amortized analysis are: aggregate analysis, the accounting method and the potential method.

As an example, we are going to use a good ol’ stack. Ths stack has 3 operations: push, pop and multipop. Multipop pops k number of elements from the top of the stack, and for both pops it cannot pop and empty stack. Pop and push cost O(1) and multipop costs min(s,k). N is going to represent the number of sequences to be executed. 

Aggregate method

This methods consists of taking the worst case of the algorithm. So for a sequence of n operations (pops, pushes and multipops), we have to ad up each of the elemental operations. So a secuence of n pushes would cost O(n), a sequence of n pops or multipops (provided they are enough elements in the stack) is O(n). If we add the 3 methods on a sequence of n operations, the running time would be O(n). Why not o(n^2)? Since both pops depend on the number of pushed element of the stack, then we would have at most n pop operations on a stack. Finally, to detemine the amortized cots would be O(n) / n = 1. 

Accounting method

On the accounting method, we assigned different costs to each operation (some more that what they really cost). We assign credit for some opperations to pay later on for the more expensive operations. 

On the stack example, pop and push cost 1 and multipop costs min (s,k). Since we know that pop and multipop depend on push, then we can put extra credit on push operations, so that we can pay pop and multipop in advanced. Remember that we cannot pop more than the numbers of elements currently in the data structure. The cost of the 3 operations are now: Push = 2,  Pop = 0, Multipop = 0

Potential method

Instead of representing prepaid work as credit stored with specific objects in the data structure, the potential method of amortized analysis represents the prepaid work as “potential energy.” The potential method works as follows. We will perform n operations, starting with an initial data structure D0. For each i D1, D2, ... , Di be the data structure that results after applying the i th operation to data structure Di1. A potential function is defined as 

Where Tactual is the cost of the operation (ex. pop = 1), plus the change of potential inside the data structure before and after the operation is performed. 

We have learned how to implement the dynamic programing techinque to solve problems with optimal substructures. Now let’s look at a similar technique: Greedy algorithms. Greedy algorithms share the optimal substucture, and memo table from DP, so what’s the difference? 

First of all when deciding on how to solve each solution, we make desicion based on the best solution for that particular set of problems raher than choosing the most optimal solution overall. We are relying that by choosing the ‘greedy’ solution on each sub problems, then we will solve the problem (based on the chain of greedy choices made througout the top down solution (another big difference between the 2). 

Now let’s see an example. Suppose we have to make an algorithm to shedule the most amount of activities in a day out of a list of activities starting at different times a day. Some activities can start when other are ‘running’, so we have to choose the most ammount of activities. We are given a list of all the possible activities in a day and their starting and finish time.They are sorted in increasing order of finishing time. Here is said table of possible activities:

 i  | 1 2 3 4 5 6 7 8 9 10 11 si | 1 3 0 5 3 5 6 8 8 2 12 fi  | 4 5 6 7 9 9 10 11 12 14 16

Our intuition is that we first choose the first activity, then we check for the next activity that has a start time (si) after finish time (ft) of the previous activity. This means that we won’t do a permutation of all possible combinations of activities, until we find the most optimum one. We just choose the best activity that bests fits the current state of the algorithm.

Does this give us the best solution? Not neccesary, since we din’t try all combinations of activities, then we might miss better solutions. Turns out that for this problem, it results in a solution that is just optimum enough to use. Checking for all permutations can get very high running time, so this solutions gives us an adequate solution that runs rather efficiently in O(n). Remember that the optimum substructure of greedy choices result in an efficient greedy solution. 

Remember when I told you how that we where goint to learn about how we can design algorithms efficiently form the start. Then dont worry that we got you covered! 

First of all let’s state what a sub problem is. So we have this big problem that we want to solve, and we look for similar and smaller solutions to that initial problem. Most of the times the first set of sub problems are still hard to solve themselves, so we create sub problems from those sub problems. We continue on unitl we have such a simple sub problem that is solved. Then those bottom sub problem can join to solve the more intermidiate subproblems, until we reach the top problem we wanted to solve, and wemagaged to solve the initial problem. All problems that can be solved this way aare said to have optimal substructure. 

Does that style of programming remind you of anything? YES: Recursion! If we can identify the optimal substructure of an algorithm, we can then apply dynamic programming to solve an algorithms. Let us try a quick example:

5! = 5*4*3*2*1 or 5! = 5*4!  .... n! = n*(n-1)!

To calculate 5!, we need to know 4! first, and to calculate 4! we need to know 3! and so on. The bug problem is calculate 5!, the intermidiate solutions would be 4! or 3! etc, the base sub problem is 1!, which is defined as 1! = 1. Therefore we divide 5! into 5*4! and divide it to 5*4*3! and so on, until we reach 1. Then we go back up, and start multiplying the known values, until we reach 5! the top of the subproblem. This type of design is called bottom-up calculation.

This is great! We can implement this for any natural number! Let’s say just after that calculation we want to calculate another factorial number, like 9! Then we have to calculate 8!, 7!, ... , and so on first. The way our algorithm is defined, we have to do all that work again, including the previously calculated 5! Calculating 5! over and over again can be very time consuming! 

Now we introduce you memoization. Memoization is nothing else than storing different values of a sub problem on a table (ex. arrays), so instead of calculating the whole sub problem again, we check the table to see if we have previous records of a solution of a sub-problem. So now When we calculate 7! after 5!, we only have to calculate 6! and 7! This greatly improves the running time of an algorithm! 

In summary, dynamic programming can be described as finding the optimal substructure of a problem, building a bottom up recursion solution for each sub problem, and storing the solution of each sub-subproblem on a memoization table (memo-table for short).