What is an Adversary?

What is an Adversary?

• A Second Algorithm Which Intercepts Access to Data Structures
• Constructs the input data only as needed
• Attempts to make original algorithm work as hard as possible
• Analyze Adversary to obtain lower bound

Previous slide

Next slide

Back to the first slide

View Graphic Version