Most Algorithms transform input objects into output objects. The running time typically grows with the input size. Average case time is often difficult to determine. We focus on the worst case running time, as it's easier to analyze and its crucial to applications such as games, finance, and robotics.
### Space Complexity
In algorithms, you need to think about the amount of space, memory, that you need to compute the algorithm.
Need to think about how complex an algorithm is in implementation, the simpler the better. Code organization is also important in the structure.
### Fibonacci
Algorithm which uses array to store previous fib numbers vs one which uses constant number of variables to compute the sequence. Space complexity varies between the two between one being O(n) and one is O(1).
The naive recursive solution for this problem is very bad. By using multiple return values we can make the recursive algorithm equal to the non-recursive algorithm.
### Counting Primitive Operations
The algorithm described is a simple implementation to find the max value of an array containing only numbers
By inspecting the pseudo-code, we can determine the maximum number of primitive operations executed by an algorithm, as a function of the input size.
Looking at the number of times n is used, in the worst case scenario, we can see a for loop, as well as other stuff? ending up with a number of operations of 8n-2, with a big O of O(n)
In the case where the denominations are always larger/equal to 2 of the smaller denominations then it makes sense when giving change, to simply give the largest coin available.
Given a set S of n items, with each item i having a positive benefit factor, b, and a positive weight, w.
Goal: Choose items with maximum total benefit but with weight at most W.
If we are allowed to take factional amounts, then this is the fractional knapsack problem. The objective is to maximize the benefit given the amount divided by the weight, with the constraint that the amount is less than the total amount W.
