This question requires us to think about running times as a function of the size of the coin array V. This question is more complex than it first appears because there are a number of different corner cases. Many of these are dependent upon the relationship between the change value, A, and V.
Take the case where A = V[len(V)-1]. An example would be A=50 with V=[1,5,10,25,50]. In this case greedy will run in O(1) time because it will take the very first coin it looks at and the problem will be solved. We could modify the coin array such that V=[1,2,3,...,48,49,50], increasing the size of V by a factor of 10, and have absolutely no effect on the runtime of the greedy algorithm.
On the opposite end of the spectrum would A=53 with V=[1,5,10,25,50]. In this case, because 53 is a prime number, greedy will run in O(V + A) time because the problem can only be solved with a 50 cent coin and 3 one cent coins (value of 1). In this case modification of the coin array such that V=[1,2,3,...,48,49,50], increasing the size of V by a factor of 10, will have an effect on the runtime of the greedy algorithm.
The complex relationship between change A and coin array V is on display in the following two plots which were generated with identical code. Coin arrays of sizes 1 to 1000 (with coin values 1 to <= 5000) and change values from 1 to 30 were randomnly generated and run through both the greedy and DP algorithms. The entire exercise was repeated 10 times and the average runtimes are plotted below. Both plots display the mostly linear relationship between length of V and runtime, the first plot exhibits quite a bit of scatter from about 100 < len(V) < 200 and again from about 550 < len(V) < 850. The exact arrays and change values were not stored so we can only speculate on the nature of the relationships between A and V in these noisy regions.
We also spent some time investigating whether any noise was being introduced by our letting change A randomnly vary between 1 and 30. So we ran the experiment again. We tried various fixed values of A and observed two things. The first observation is that fixing the value of A dramatatically cuts down on the noise in the plot. Secondly, a larger value of A only changes the plot in that it changes the slope of the DP curve. The effect on the greedy curve is minimal, especially for larger values of A, because it starts to dominate over len(V). One such plot with fixed value A=100 is shown below.
Finally, we wanted to create at least one plot looking at the slow change algorithm. We used the same code as above but fixed change A at 20 for runtime purposes. Increasing A to a higher value was uneccessary to understanding how the slowchange algorithm responds to increasing size of coin array V. The plot below shows that the slowchange algorithm is actually worst for the smallest size of V and dramatically and quickly improves as size of V increases. This behavior is due to the fact that as the size of V increases, the number of base cases increases. The base cases allow the algorithm to terminate without entering further recursive calls. In the case where V = [1], the recursion must run all the way to the bottom. In essence, adding elements to V decreases the "full-ness" of the recursion tree.