19.6.2. Time Complexity Conclusion

Try these first

1. 1.

   What is a greedy algorithm?

   Hint

   Think about how you make decisions under constraints.

2. 2.

   Can you provide an example of a problem where a greedy algorithm works?

   Hint

   Consider problems involving weight optimization.

3. 3.

   What is the main goal of greedy algorithms?

   • To achieve a global optimum
   • To maximize local benefits
   • To minimize complexity

   Hint

   Consider the purpose of optimization.

4. 4.

   True or False: Greedy algorithms always work for every optimization problem.

   • True
   • False

   Hint

   Reflect on examples where greedy methods fail.

5. 5.

   Given a set of intervals, write the algorithm in pseudocode to solve the scheduling problem using the greedy approach.

   Hint

   Consider which intervals to filter out at each step.

6. 6.

   If there are n intervals, analyze the steps your algorithm takes through a worst-case scenario. What is the implication of this for its complexity?

   Hint

   Think about how many times you’d check for overlaps in strict conflict scenarios.