In the far away land of coinsville, they use $4$ different coins as currency, $\{1,10,100,200\}$
What is the computational class of the amount of coins (minimal!!) we need to get $k$ amount?
Well, the obvious best solution is to get as many coins of $200$ as we can, then as many $100$, then as many $10$ and finally $1$.
We will need exactly $\alpha=\lfloor\frac{k}{200}\rfloor$ coins of $200$. In the same manner, we need $\beta=\lfloor\frac{k-200\alpha}{100}\rfloor$ coins of $100$ and so on, in the end this will be bounded by some polynomial of $k$ so I'd say we need $\Theta(k)$. is this correct? Because this doesnt sit right with some examples. For example if $k=1000$ then we need exactly $5$ coins, not a lot, thats not a polynonmial of $k$...my logic dictates that it will be $\log(k)$ but the math does not agree with my logic.
Let $f(k)$ be the number of coins needed. You need $\left\lfloor\frac{k}{200}\right\rfloor$ coins of value $200$. After that you need at most one coin of value $100$, nine coins of value $10$, and nine coins of value $1$, so
$$\frac{k}{200}-1<\left\lfloor\frac{k}{200}\right\rfloor\le f(k)\le\left\lfloor\frac{k}{200}\right\rfloor+19<\frac{k}{200}+20\;.$$
It does appear that $f(k)$ is $\Theta(k)$.