8.1 Greedy Algorithms

Question 1

What is the runtime complexity for the greedy recursive algorithm and why

Answer 1

theta(n). as the runtime is dominated by incrementing m. It can never go > n and then recursions don’t restart m.

Question 2

What is the runtime complexity for the greedy iterative algorithm and why is it better than recursive

Answer 2

theta(n). simpler to understand. don’t need to save each stack frame to memory.

Question 3

What is the generalised greedy strategy?

Answer 3

1. check if problem exhibits the optimal substructure property
2. Develop a recursive solution
3. show that with a greedy choice only one sub-instance remains
4. show that the greedy choice is ‘safe’ (exchange argument)
5. Design a recursive greedy algorithm
6. Convert to an iterative algorithm